Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networks
Authors: Andong Wang
Chao Li
Mingyuan Bai
Zhong Jin
Guoxu Zhou
Qibin Zhao
Venue: NeurIPS 2023 poster (2023)
Keywords: Tensor SVD; Tensor Neural Networks; Transformed Low-rankness; Adversarial Generalization; Implicit Bias.
TL;DR: For the first time, we conduct a theoretical analysis of how transformed low-rank parameterization benefits the robust generalization of neural networks with t-product layers (t-NNs).

Abstract: Multi-channel learning has gained significant attention in recent applications, where neural networks with t-product layers (t-NNs) have shown promising performance through novel feature mapping in the transformed domain. 
However, despite the practical success of t-NNs, the theoretical analysis of their generalization remains unexplored. We address this gap by deriving upper bounds on the generalization error of t-NNs in both standard and adversarial settings. Notably, it reveals that t-NNs compressed with exact transformed low-rank parameterization can achieve tighter adversarial generalization bounds compared to non-compressed models. While exact transformed low-rank weights are rare in practice, the analysis demonstrates that through adversarial training with gradient flow, highly over-parameterized t-NNs with the ReLU activation can be implicitly regularized towards a transformed low-rank parameterization under certain conditions. Moreover, this paper establishes sharp adversarial generalization bounds for t-NNs with approximately transformed low-rank weights. Our analysis highlights the potential of transformed low-rank parameterization in enhancing the robust generalization of t-NNs, offering valuable insights for further research and development.

Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networks
Andong Wang RIKEN AIP
Chao Li RIKEN AIP chao 110.1110rkken.
Mingyuan Bai RIKEN AIP
andong wangoriken.jp jp
mingyuan. bai jp
Zhong Jin
Guoxu Zhou"
China University of Satroleum-Bejjing at Karamay zhongjin in@cupk edu. cn
Guangdong University of Technology gx zx.zhouggdut. edu. cn
Qibin Zhao RIKEN AIP qibin www.oriken.....
Abstract
Multi-channel learning has gained significant attention in recent applications, where neural networks with t-product layers (t-NNs) have shown promising performance through novel feature mapping in the transformed domain. However, despite the practical success of t-NNs, the thcoretical analysis of their generalization remains unexplored. We address this gap by deriving upper bounds on the generalization er- ror of t-NNs in both standard and adversarial settings. Notably, reveals that t-NNs compressed with exact transformed low-rank parameterization can achieve tighter con-oopreseed models. While
adversarial generalization bounds compared exact transformed low-rank weights are rare in practice, the analysis demonstrates that through adversarial training with gradient flow, highly weer-parameterized t-NNs with the ReI.U activation can be implicitly regularized towards a trans- formed low-rank parameterization under certain conditions. Moreover, this paper establishes sharp adversarial generalization bounds for t-NNs with approximately transformed low-rank weights. Our analysis highlights the potential transformed low-rank parameterization in enhancing the robust generalization of t-NNs, offering valuable insights for further research and development.
Introduction
Multi-channel learning is 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 [24, 39, 60, 61]. Among the methods tackling this task, neural networks with t-product layers (t-NNs,
Eq. (5) for a typical example) [12, 36) came to the stage very recently with remarkable efficiency and robustness various applications such graph learning, remote sensing, and more [1, 11, 14, 32. 38, 39, 53, 58]. What distinguishes t-NNs from other networks is the inclusion of t-product layers, founded on the algebraic framework of tensor singular value decomposition (t-SVD) [19, 40, 60. 61]. Unlike traditional tensor decompositions, t-SVD explores the transformed low-rankness, i.e., the low-rank structure of tensor in the transformed domain under an invertible linear transform [18]. The imposed transform in t-product layers provides additional expressivity to neural networks, while
"Qibin Zhao and Guoxu Zhou are the corresponding authors.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the controllable transformed low-rank structure in t-NNs enables a flexible balance between model accuracy and robustness [36, 38, 53].
Despite the impressive empirical performance of t-NNs, the theoretical foundations behind their success remain unclear. The lack of systematic theoretical analysis hinders deeper comprehension and exploration of more effective applications and robust performance of t-NNs. Furthermore, the inclusion of the additional transform in I-NNs renders the theoretical analysis more technically challenging compared to existing work on general neural networks [29, 37, 43, 55J. To address this challenge, we establish for the first time a theoretical framework for t-NNs understand both the standard and robust generalization behaviors, providing both theoretical insights and practical guidance for the efficient and robust utilization of t-NNs. Specifically, we address the following fundamental questions:
Can we theoretically characterize the generalization behavior of general t-NNs? Yes. We derive the upper bounds the generalization error for general t-NNs in both standard and adversarial settings in Sec. 3.
How does exact transformed low-rankness inftuence the robust generalization t-NNs? In Sec. 4.1, our analysis shows that t-NNs with exactly transformed low-rank weights exhibit lower adversarial generalization bounds and require fewer samples, highlighting the benefits of transformed low-rank weights t-NNs for improved robustness and efficiency.
How does adversarial learning of I-NNs affect the transformed ranks of their weight tensors? In Sec. 4.2, we deduce that weight tensors tend be of transformed low-rankness approximately for highly ever-parameterized t-NNs with ReLU activation under adversarial training with gradient flow.
How robust generalization impacted by approximately transformed low-rank weight tensors in I-NNs? In Sec. 4.3, we establish sharp adversarial generalization bounds for t-NNs with approxi- mately transformed low-rank weights by carefully bridging the gap with exact transformed low-rank parameterization. This finding again underscores the importance of incorporating transformed low-rank weights as a means to enhance the robustness of t-NNs.
2 Notations and Preliminaries
In this section, we introduce the notations and provide a concise overview of t-SV and t-NNs, which play central role in the subsequent analysis.
Notations. We use lowercase, lowercase boldface, and uppercase boldface letters to denote scalars, egg,, a E RR vectors, e.g., E IRm,, and matrices, e.g., A E RR respectively. Following the standard notations in Ref. [19], 3-way tensor of size x 1 is also called a r-vector and denoted by underlined lowercase, e.g. whereas 3-way tensor of size m x n X is also called I-matrix and denoted by underlined uppercase, e.g., . X. We use a t-vector X E [Bdx1xe xe to represent a multi-channel example, where denotes the number of channels and d is the number of features for each channel.
Given matrix A E RMX=, its Frobenius norm (F-norm) and spectral norm are defined as || == / E minu/m.n) of and ||A||| == max; oi respectively, where di, i i= 1,,,. min min(m. n) are its singular values. The stable rank of a non-zero matrix A is defined as the squared ratio of its F-norm and spectral norm (A) = |A| || Given a tensor T. define its Ip 1p-norm and F-norm respec- tively as [T,,, = ||vec (T) I1, and [T = [[vec where vea(.) denotes the vectorization operation of tensor [21]. Given T E B.x let T denote its 7th frontal slice. The inner product between two tensors A. B is defined (A, B) vec(A) vec(B). BB. The frontal-slice-wiss product of two tensors A. B. denoted by A @ B. equals tensor T such that T...: = A..,,B...i i 1,... [19]. We use - as the absolute value for a scalar and cardinality for a set. We use o to denote the function composition operation. Additional notations will be introduced upon their first occurrence.
2.1 Tensor Singular Value Decomposition
The framework of tensor singular value decompasition (t-SVD) is based on the t-product under an invertible linear transform M [18]. recent studies, the transformation matrix M defining the transform M is restricted to be orthogonal [50] for better properties, which is also followed in this

---

paper. Given any orthogonal matrix M E Re define the associated linear transform M() with its inverse M (-) on any T E mxxxx
M(T) = = T M. and M (T) == X3 M
(I)
where X3 denotes the tensor matrix product on mode-3 [18].
Definition (t-product [18]). The t-product of any A Rmxax and B E Bnnxxx under transform
M in Eq. (1) is denoted and defined A * M B = C E Rmxkxe such that M (C) (() M (B) in the transformed domain. Equivalently, we have C M (M(AA O (B) in the original domain.
Definition (M bloock-diaggoal matrix). The Miblook-diagoonl matrix of any T E Rmxxxe denoted by M, is the block diagonal matrix whose diagonal blocks are the frontal slices of M(T):
(T)...
M M
TM == bdiag (M =
E Rexxxe
M(T)
In this paper, we also follow the definition of t-transpose, t-identity tensor, t-orthogonal tensor, and f-diagonal tensor given by Ref. [18), and thus the t-SVD is introduced as follows.
Definition 3 (t-SVD, tubal rank [18]). Tensor Singular Value Decomposition (t-SVD) E Rmxaxe under the invertible linear transform M in Eq. (1) is given as follows
T x S S
(2)
where U E Rmxmxx and V E RExaxe are t-orthogonal, and S E Rmxxxx is f-diggonal. The tubal rank of T defined as the number of non-zero tubes of S in its t-SVD in Eq. (2), i.e. (T) = {i i,;, # 0, S min(m, n.,nnH. n.H
For any T E mx with the tubal rank (T), we have following relationship between its t-SVD and the matrix SVD of its M-block-oee -iaaoca- matrix [26, 50]:
T U S V
T UM -.M V and C. MT))
(3)
As the M wl-bbock-din diiggoaa matrix Tas defined after transforming tensor T from the original domain to the transformed domain, the relationship c (T) 2 rank indicates that the tubal rank can be chosen measure of transformed low-rankness [26, 50].
2.2 Neural Networks with t-Product Layer (t-NNs)
In this subsection, we will introduce the formulation of the t-product layer in t-NNs, which is designed for multi-channel feature learning.
Multi-channel feature learning via t-product. Suppose we have a multi-channed example repre- sented by t-vector E Rdx1xe, where is the number of channels and d is the number of features. We define an L-layer t-NN feature extractor f(x), to extract di features for each channel of x:
f(x)
(L) xx):
(())
(w() M (1-1)) (x), 1- 1,...
(())
(4)
where the 1-th layer (1) first conducts t-product with weight tensor (t-matrix) w(() Rdixdi 1xc on the output of the 1)-th layer as multi-channel features² (() (x) 1 xlxe obtain
(dz x 1 x c)ddimensional representation and then uses the entry-wisely ReLU activation ( = max (x. 0} for nonlinearity.
Remark. Unlike Refs. [36]. [32] and [53] 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.
For simplicity, do by treating the input example x as layer (0)
"Although we consider ReLU activation in this paper, most of the main theoretical results (e.g., Theorems 3, 12, and 14) can be generalized general Lipschitz activations with slight modifications in the proof.
3

---

By adding a linear classification module with weight w E R after the feature exaction module in Eq. (4), we consider the following t-NN predictor whose sign can be utilized for binary classificationn
(x W) = w -ecl (
(x)) E
IR.
(5)
Let W- (W()) W(C)
w be the collection of all the weights'. With a slight abuse of notation, 2 + Σ Ii
it denote the Euclidean norm of all the weights. The function class of general t-NNs whose weights are bounded in the Euclidean norm is defined as
let [| Ip := V [| 2
1 1, 1.,.,..... } ..). / ||= S B1,
8 = (
(f(x: W)
||w||2 S Bus
(6)
with positive constants Bw: and B = 1, L. Let Bw == Bu I Br for simplicity.
Stannan
Standard and Robust Generalization Seneralization Bounds for t-NNs
3
This section establishes both the standard and robust generalization bounds for any t-NN f E B.
Generalization
3.1 Standard Generalization for General t-NNs
Suppose we are given training multi-channel dataset S consisting of N example-.. pairs ((x, W)) C IRdxIxG x [+1} i..dd drawn from an underlying data distribution Ps.v- WEl
Assumption 1. Every input example x E Rdx1xe has an upper bounded F-norm, i.e., |x]|| S Bz. where Bg is positive constant.
When a loss function (x)x)) w) is considered the measure of the classification quality, we classificated
define the empirical and population risk for any f E 3 as L(f) == N " (x,(),, ys) and r
L(f) == EE [x) y)], respectively. Similar to Ref. [30], we make assumpttos on the loss as follows.
Assumption 2. The loss E(h(x) y) can be expressed as ((h(x),v) = exp(-f(yh( for any I-NN
E 3, such that:
(A.1) the range of loss ((.,)) is [0, B), where B is a positive constant;
(A.2) ( function f: IR + R is C smoothh
(A.3) ((x) 2 0 for any E;
(A.4) there exists by 2 0 such that (x) is non-decreasing for (bp, +00), and the derivative af((2) (2) (a+) + +oc as I + +oo;
(A.5) let g: : [[bb)), +00) + [b,, 20) be the inverse function of ī on the domain [br, +00). There exist ba max (T(r)), f(2b,)) and K > 1, such that g' (z) S (0x) and f'()) S (gy(
for any x E (bg. +x0),y y E (0(bg), +oo) and 0 E [1/2, 2.
1).
Assumption (A.1) is a natural assumption in generalization analysis [3, 59], and Assumptions (A.2)- (A.5) are the same as Assumption (B3) in Ref. [30]. According Assumpttonn Issumption (A.2), the loss function -()-)) satisfies the L Lipicchti continuity
(effte (((h())) (1) - ((h(x,), v2)1 s Lelyn((x;) (2(x2)), with L+ = suppisn, ('())e f(a), (7)
where B₁ is an upper bound on the output of any I-NN h E 8. The Lipschitz continuity is also widely assumed for generalization analysis of DNNs (55, 59). Assumption 2 is satisfied by commonly used
loss losstiil functions such as the logistic loss and the exponential loss.
renerraan (Generalization Ceerzizatiiiooiiiii bound for t-NNs). Under Assumpttion I and 2, it holds for any f E $ that Lemma 3
The
The generalization gap [(f) - Ł(f)) of any function f E 3 can be bounded as follows.
L Bz Bw (v (Vllog2((L+))) 1))
Bw
[(f) - -()) <
3B
(8)
with probability b at least 1 -e for any t > O.
VN
2N
Here for the ease of notation presentation, use the tensor notation W instead of the notation W.
4

---

Remark. When the input example has channel number c= 1, the generalization bound in Theorem 3 is consistent with the E-norm-based bound in Ref. [8].
3.2 Robust Generalization for General t-NNs
We study the adversarial generalization behavior of t-NNs in this section. We first make the following assumption on the adversarial perturbations.
Assumption 4. Given an input example X. the adversarial perturbation is chosen within a radius- ball of norm Ra(-) with compatibility constant [35] defined as CR, :- supx=0 Rs /x) [
The assumption allows for much broader adversary classes than the commonly considered lp batttacks [54, 55J. For example, if one treats the multi-channel data E gdx1xe as matrix of dimensionality x с and attacks it with nuclear norm attacks [17]. then the constant CR. - /min(d, cj.
Given an example-label pair (x, y). the adversarial loss for any predictor f is defined as {(f(x). v) = max R, -x {(f(x) v)- The empirical and population adversarial risks are thus defined as Cudv (f) == N - (x)(x) y4) and (=²(()) Ep [
[f( (x), v]], respectively. The adver- sarial generalization performance measured by the adversarial generalization gap (AGP) defined as Ludv (f) - (f). Let B- == (B2 + (CR,) Bw. Bw. For any f E 3. its AGP bounded as follows.
Theorem 5 (Adversarial generalization bound for t-NNs). Under Assumptions 1, 2, and 4, there exists a constant C such that for any ʃ E B, holds with probability least 2e (VI. 0):
Cuby (f) -Lube
Eudy (f) S
CL.Bj VN
d
3B
t 2N
(9)
Remark. When the input example has channel number с c and the attacker uses b attatkkkk, the adversarial generalization bound in Theorem 5 degenerates the one in Theorem 4 of Ref. [55].
4 Transformed Low-rank Parameterization for Robust Generalization
4.1 Robust Generalization with Exact Transformed Low-rank Parameterization
According to Theorem 5, the AGP bound scales with the square root of the parameter complexity, specifically as O( c((c - dd)/N). This implies that achieving the desired adversarial accuracy may require large number N of training examples. Furthermore, high parameter complexity leads increased energy consumption, storage requiremetts, and computational cost when deploying large embedded and mobile devices.
t-NN models, particularly on resource-constrane
To this end, propose transformed low-rank parameterization scheme to compress the original t-NN models 8. Specifically, given a vector of pre-set ranks r = "n.."" E RL where s min(de d, we consider the following subset of the original t-NNs:
3. := (= 3, and ri (W()) S rI, 1 1= I).
(10)
In the function set 3r. the weight tensor ( of the 1-th layer has the upper bounded tubal rank, which means low-rankness in the transformed d We bound the AGP for any f E 3r as follows.
Theorem 6 (Adversarial generalization bound for t-NNs with transformed low-rank weights). Under Assumptions 2, and there exists constant C' such that
CeL
1. Σ
rild-1 + di) log( + 1)) + 3B,
(1I)
VN
2N
holds for any ft E 3r with probability least 1 -t (Vt > 0).
For empirical implementations, one can adopt similar rank learning strategy to Ref. [15] to select a suitable rank parameter Due to the scope of this paper, leave this for future work.
5

---

Comparing Theorem 6 with Theorem 5, we observe that the adversarial generalization bound under transformed low-rank parameterization has a better scaling, specifically Of D(vcL> m di))N This also implies that smaller number N of training examples is required to achieve the desired accuracy, as well as reduced energy consumption, storage requirements, and computational cost. Please refer Sec. A.1 in the appendix for numerical evidence.
4.2 Implicit Bias of Gradient Flow for Adversarial Training of Over-parameterized t-NNs
Although Theorem 6 shows exactly transformed low-rank parameterization leads to lower bounds, the well trained t-NNs on real data rarely have exactly transformed low-rank weights. In this section, we prove that the highly peremaaramtee t-NNs, trained by ad adversarial training with gradient flow (GF), are approximately of transformed low-rank parameterization under certain conditions.
First, the proposed t-NN fx: W) is said to be (positively) homogeneous as the condition f(; aW) a f(x: W) holds for any positive constant a. Motivated by Ref. [29], we focus the scale invariant adversarial perturbations defined as follows.
Definition 4 (Scale invariant adversarial perturbation [29]). An adversarial perturbation d. (W) is said to be scale invariant for (xx W) al any given example X; if satisfies (,W))) 5. (W) for any positive constant a.
Lemma 7. The 12-FGM [34], FGSM [9]. P2D and lx PGD [31] perturbations for the t-NNs are all scale invariant.
Then, we consider adversarial training t-NNs with scale invariant adversarial perturbations by GF, which can be seen as gradient descent with infinitesimal step size. When using GF for the ReLU t-NNs, W changes continuously with time, and the trajectory of parameter W during training is an are W: [0, oo) + [dim(W), W(t) that satisfies the differential inclusion [7, 30]
dW(() E -
Gadv (W())
(12)
dt
for t 2 0 a.e., where d Ladv denotes the Clarke's subdifferential [7] with respect to W(t). If Ludv (W) is actually a -'-moooth function, the above differential inclusion reduces to
dW(() aaay (()))
(13)
(
for any t 2 O, which corresponds to the GF with differential in the usual sense. However, for simplicity, we follow Refs. [45, 46) and still use Eq. (13) to denote Eq. (12) with a slight abuse of notation, even if Ludv does not satisfy diffcrentiability but only local Lipschitzness 6
We also make assumption on the training data follows.
Assumption 8 (Existence of a separability of adversarial examples during training). There exists time to such that Lady (lo) < N-1
This assumption is a generalization the separability condition in Refs. [29, 30J. Adversarial training typically achieve this separability in practice, i.e., the model can fit adversarial examples of the training dataset, making the above assumption reasonable. Then, we obtain the following lemma.
Lemma (Convergence the direction of KKT point). Consider the hypothesis class 3 in Eq. (6). Under Assumptions 2 and 8, the limit point of normalized weights (W(L)/ W( 12 0} of the GF for Eq. (13), ie., the empirical adversarial risk with scale invariant adversarial perturbations 8 W), is aligned with the direction of KKT point of the minimization problem:
min W 2
s.t. y:f(y + WW): 2, i 1= N.
(14)
Building upon Lemma 9, establish that highly wer-paramettrized t-NNs undergoing adver- sarial training with GF will exhibit an implicit bias towards transformed low-rank weights.
'Note that the ReLU function is not differentiable at O. Practical implementations of gradient methods define the derivative o' (0) to be constant in [0, 1). In this work assume for convenience that o' d'(0) = 0.

---

Theorem 10 (Implicit low-rankness for t-NNs induced by GF), Suppose there is an example x,
satisfying |R& S 1 in the training ser S {(x; b:)) Suppose there (J 1)-layer (J 2 2)
ReLU I-NN, denoted by 9(x Y) with parameters V (V y((), v), satisfying the conditions:
(C.1) the dimensionality of the weight tensor yui E E Xm=xxx-- of the j-th 1-product layer satisfies my 2 2, -,....
(C.2) there is constant B. O, such that the Euclidean norm of the weights V
(V()) V(L), satisfy | S B, for any j ,,.., and [2 Boi
(C.3) for all E (1,...,), NN,, have V 5, V. V) 2
Then, we consider the class of pver-marameterized t-NNs {f(x: W)} defined in Eq. (5) satisfying
(C.4) the number of t-product layers is much greater than J:
(C.5) the dimensionality of weight W E Rdixd-ixx xc satisfies di > maxzgr(m;) for any S L.
Let W (W*(), ( w*) ) be a global optimum of Problem (14). Namely, W parameterizes a minimum- norm t-NN fx: W E & that labels the perturbed training set correctly with margin under scale invariant adversarial perturbations. Then, have
-1/2
El
Fsub W
(1) M
(1+
B
(em))()
where W (l)
M denotes the M M-block-diagonal matrix of weight tensor (!(() for any I - 1,..... L.
By the above theorem, when L is sufficiently large, the harmonic mean of the square root of the stable
rank of W (1)
i.e. the -ibbooc--diagonal matrix of weight tensor (1) is approximately bounded by /cm,, which significantly smaller than the square root of the dimensionality /minfcdi, cdi-1 1 according to condition (C.5) in Theorem 10. Thus, / (x: W") has nearly low-rank parameterization in the transformed domain. In our case, the weights W( generated by 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 norm and the F-norm invariant to scaling, and hence it suggests that after a sufficiently long time, GF tends to reach t-NN with transformed low-rank weight tensors. Refer to Sec. A.2 for numerical evidence supporting Theorem 10.
4.3 Robust Generalization with Approximate Transformed Low-rank Parameterization
Theorem 10 establishes that for highly over per-paarametriiee adversarial training with GF, well-trained t- NNs exhibit approximately transformed low-rank parameters under specific conditions. In this section, we analyze the AGP of t-NNs that possess an approximately transformed low-rank parameterization'
Initially, by employing low-tubal-rank tensor approximation [20], can always compress an approximately low low-tubal-rank parameterized t-NN f by a t-NN g E 3. with an exact low-tubal-rank parameterization, ensuring small distance between g and f in the parameter space. Now, the question is: Can the small parametric distance between f and g also indicate a small difference in their adversarial generalization behaviors? To answer this question, we first define the (ō, a)pppooxiiat low-tubal-rank parameterized functions.
Definition 5 (66, aaapprooiietee low-tubal-rank parameterization). A I-NN f(x: W) E $ with weights W- = (w, (11) ... w(L)) said to satisfy the (ō. -aapproximmaee low-tubal parameterization with tolerance 8 > 0 and rank (ri,.-- .TL) NL4 if there is I-NN 9(x: W,) E 3, whose weights w(!)) satisfy w w(O [|e S 8 for any 1= 1= ,.
W (w, w(!) ri
Furthermore, let's consider the collection of t-NNs with approximately Jow-tubal www-tuubl--ant. rrank weights
3g.r = {f E satisfies the (5, approxiitee low-tubal-rank parameterization).
(15)
'ee use the tubal rank as a measure of low-ranknes in the transformed domain for notation simplicity. One also consider the average rank [52] multi-rank [50] for more refined bounds with quite similar techniques.
7

---

Subsequently, we analyze the AGP for any f 3&, in termss of its low- www-uubl--aank compression E 3r- The idea is motivated by the work on compressed bounds for con-compressed but compressible models [43], originally developed for generalization analysis of NNs for standard training.
Under Assumption 2, we first define 3 == { (x, v) + min (/(( I E 8ar}
as the adversarial version of B6.r To analyze the AGP of f E 35.r through E Br. we instead consider their adversarial counterparts f E 3ør and 9 E Bady, where Bp is defined as S, {g- (x. y) + minn, s's (x('') g E Jr). Define the Minkowski difference of B and 8 as 83. 3. = (/ / E ggr
" The empirical L2-norm of a t-NN h E 3 on the
training data S = {x,, = is defined as ||Alls == / / - (x, Vi), and the population L2-norm is ||fe|Lz == / h22 (x. v)]. Define the local Rademacher complexity of 8% 3 of radius t > as (B 3. == Rv ((h E 83r spdt ||All,, S $t)), where RN (H) denotes the average Rademacher complexity of a function class H [4].
The first part of the upcoming Theorem 12 shows that a small parametric distance between f and leads to small empirical Ly- diiddittece in the adversarial output space. Specifically, for any f(x: W) 3or with compression (xx: W,), their (adversarial) empirical Læ-distance [ W) (x: W, W,) can be bounded by small constant é > O in linearity of 8. We also aim for small population L2-distance by first assuming the local Rademacher complexity Re (B%. - ) can be bounded by a concave function of t, following common practice in Rademacher complexity analysis [4, 43].
Assumption 11. For any > 0, there exists a function Φ(t)= [0, - [0, oo) such that Re 32th)) S ((t) and (2t) s 26(().
We further define t, = (4)= =- inf {+> 0 16 16 + B V 1M/N++113,//// S 1/2
for any t > 0, such that the population L2-norm of any h E 3 - 3. can be bounded by |1A122 < 2(111| + ) using the peeling argument [42, Theorem 7.7]. We then establish an adversarial generalization bound for approximately low-tubal-rank t-NNs as follows.
Theorem 12 (Adversarial generalization bound for general approximately low-tubal-rank t-NNs). (I). For any f E Bo. with adversarial proxy f E 3ady there exists a function g E Br with adversarial
proxy ğ E Badv, such that the empirical Lz-distance || ğlls S Et B =: f.
(II). Leti == 2(2 + +t). Under Assumptions 1, 2, 4, 11, there exist constants C1, C2 > O satisfying
C.LeB VN
(at Ludi (
rild
+ B
2N
main term
(16)
t ((t) + L.t
B
+ C2
N
N
term
for any f E 3ä. with probability at least -e 1e=' for any t >> O, where (D() is defined as
((t) : :R (feof- -o f sadv 9 E gadv Il - 301.,,111 st}).
The main term of the bound quantifies the complexity of functions in 3r with exact low-tubal-rank parameterization in adversarial settings, which be significantly smaller than that of S On the other hand, the bias term captures the sample complexity required to bridge the gap between approximately low-tubal-rank parameterized 8ar and exactly low-tubal-rank parameterized 3r As we usually observe ee = o(1/vN), setting i = (1) allows the bias term to decay faster than the main term, which is (l///N). Theorem 12 suggests that a small parametric distance between &a, and g 3, also implies small difference in their adversarial generalization behaviors.
special case. We also showcase specific scenario where the weights of t-product layers exhibit a polynomial spectral decay in the transformed domain, leading to a considerably small AGP bound.
8

---

Assumption 13. Consider the setting where any 1-NN f(x: W) E 36x has tensor weights wil (1 = 1,... LL) whose singular values in the transformed domain satisfy oj (M (W())..) S Vo j_
where Vo > 0 is a constant, and () is the j-th largest singular value of a matrix.
Under Assumption 13, the weight tensor W can be approximated by its optimal tubal-rank- -2 |l. I Vc/(2a - ( 1))1-20)/2 [20], which can be much smaller than | || when a > 1/2 is sufficiently large. Thus, we can find an exactly low-tubal-rank parameterized g E 3r for any f E 3ar satisfying Assumption 13, such that the parametric distance between 9 and f is quite small. The following theorem shows that the small parametric distance also leads to a small AGP.
rt approximation w for any 1 S ri S minfd;, d(-1} with error ||w() w
-
Theorem 14. Under Assumptions 1, 2, 4, and 13. we let i VoB, (i B1==B then for any I-NN f Ba,r. there exists a function g 3r whose t-product layer weights have tubal-rank exactly no greater than ru, satisfying fl ğlls S E. Further, there is constant Ca only depending on a such that the AGP, i.e. ( jady (f), of any f E B8,r can be upper bounded by
ByL + iv
2a E
BB R0eF
+ +1) + fzalT 20
E + (e+
B Le
L
+ 1B N
for any
with probability at least 1 4e where Ei N
N
Et
rid
d-1 d= (og and E2 -N- (LVoBBBT)) (di di-1) log))
1/a
This suggests that by choosing sufficiently large o: 1/2, where each weight tensor has tubal-rank close to 1, we can attain a superior generalization error bound. It is important to note that the rank ri can be arbitrarily chosen, and there exists a trade-off relationship between è and E₁. Therefore, by selecting the rank appropriately for a balanced trade-off, we can obtain an optimal bound as follows.
Corollary 15. Under the same assumption to Theorem 14, if we choose the parameter r of tubal ranks in 3r by ri min [ (LV 1/ di, d1-1), then there is a constant Ca only depending on such that the AGP of any f É B8, can be upper bounded as
c c
(INOBT')
1/0
(d + d: ( (ogg)LB/VV/)
(ata( -a CaLe B2- (a
11-1/120)
N
20 E2
20-1
B
1 1
B
+
+
E2
+
Le
N
N
with probability at least 1 - 4e 1 for any 1 1> 0.
is worth highlighting that the bound exhibits a linear dependency on the number of neurons in the t-product layers, represented as D( + di-) contrast, Theorem 5 demonstrates a dependency on the total number of parameters, denoted as O(v 1/N). This observation suggests that employing the low-tubal-rank parameterization can potentially enhance adversarial generalization for t-NNs.
5
Related Works
T-SVD-based data and function representation. The unique feature of t-SVD-based data repre- sentation, in contrast classical low-rank decomposition methods, is the presence of low-rankness in the transformed domain. This transformed low-rankness is crucial for effectively modeling real multi-channel data with both smoothness and low-rankness [24, 49, 50]. Utilized in t-product layers in DNNs [32, 36, 53], t-SVD has also been a workhorse for function representation and achieves impressive empirical performance. While i-SVD-based signal processing models have been exten- sively studied theoretically [13, 24, 27, 40, 50, 60], the t-SVD-based learning model itself has not been thoroughly scrutinized until this paper. Hence, this study represents the first theoretical analysis of --SVD-basce learning models, contributing the understanding of their theoretical foundations.

---

Theoretical analysis methods. Our analysis draws on norm-based generalization analysis [37] and implicit regularization of gradient descent-based learning [46] as related theoretical analysis methods. Norm-based generalization analysis plays crucial role in theoretical analysis across various domains, including standard generalization analysis of DNNs [8] compressed models [22], non-compressed models [43], and adversarial generalization analysis [3, 55, 59]. Our work extends norm-based tools to analyze both standard and adversarial generalization in t-NNs, going beyond the traditional use of matrix products. 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 [16, 30, 45]. We non-trin non-trivially extend these methods to analyze t-NNs and reveals that GF for over- paramettrrie ReLU t-NNs produces nearly transformed low-rank weights under scale invariant adversarial perturbations.
Our theoretical results notably deviate from the standard error bounds for fully connected neural networks (FNNs) in several ways:
The generalization bounds in Lemma 3 and Theorem 5 for t-NNs diverge from their counterparts for FNNs in Refs. [8, 55, 59] due to the channel number c in I-NNs. Moreover, Theorem encompasses wider range of adversary classes than the 1y-attacks in the aforementioned references.
The uniqueness of Theorem 6, compared to Refs. [55, 59), stems from its consideration of weight Low-ranknes, in the adversarial generalization bound, suggesting possible robustness improvements in generalization.
Our exploration of the implicit bias in GF for adversarial training presents a novel angle: the bias towards approximate transformed low-rankness in t-NNs. While Ref. [29] focuses on the implicit bias in adversarial training for FNNs, centered on KKT point convergence with exponential loss, our work delves deeper, considering wider array of loss functions in adversarial training for t-NNs.
A crucial distinction in adversarial generalization bounds, detailed in Section 4.3, from non- adversarial bounds for FNNs [43] is the integration of the localized Rademacher complexity. This encompasses the Minkowski difference between adversarial counterparts of both approximately and exactly low-tubal-rank t-NNs as seen in Theorem 12.
Concluding Remarks
A thorough investigation of the generalization behavior of t-NNs is conducted for the first time. We derive upper bounds for the generalization gaps of standard and adversarially trained t-NNs and propose compressing t-NNs with a transformed low-rank structure for more efficient adversarial learning and tighter bounds on the adversarial generalization gap. Our analysis shows that adver- sarial training with GF in highly wer-parameterized settings results in t-NNs with approximately transformed low-rank weights. We further establish sharp adversarial generalization bounds for t-NNs with approximately transformed low-rank weights. Our findings demonstrate that utilizing the transformed low-rank parameterization can significantly enhance the robust generalization of t-NNs, carrying both theoretical and empirical significance.
Limitations. While this paper adheres to the based framework for capacity control [8, 371, it is worth noting that the obtained generalization bounds may be somewhat conservative. However, this limitation can be mitigated by employing more sophisticated analysis techniques, as evidenced by recent studies [2, 25, 56, 57].
Discussions. The inclination of adversarial training towards low-rank/sparse weights, and the recip- rocal effects of parameter reduction on robustness, are currently at the forefront of ongoing research. This domain has witnessed a spectrum of observations and results [6, 23, 41, 51]. In this study, we propose that employing low-rank parameterization can enhance the adversarial robustness of t-NNs, as evidenced by our analysis of uniform adversarial generalization error bounds. However, despite these promising results, it is crucial to emphasize the necessity of a more exhaustive exploration of low-rank parameterization. Its implications, particularly when considered the context of approxi- mation, estimation, and optimization, are profound and warrant further dedicated research efforts. Such comprehensive investigation will undoubtedly enhance our understanding and fully unlock the potential of low-rank parameterization in neural networks.
10

---

Acknowledgments
We extend our deepest gratitude to Linfeng Sui and Xuyang Zhao for their indispensable support in implementing the Python code for t-NNs during the rebuttal phase. Our sincere appreciation also goes both the area chair and reviewers for their unwavering dedication and meticulous attention given to this paper. This research was supported by RIKEN Incentive Research Project 100847-202301662011 by JSPS KAKENHI Grant Numbers JP20H04249 and JP23H03419, and in part by National Natural Science Foundation of China under Grants 621031 10 and 62073087.
References
[1] An, W. Liu, Q. Liu, L. Guo, Ren, and T. Li. Dginet: Dynamic graph and interaction awaree convolutional network for vehicle trajectory prediction. Neural Networks, 151:336-380 308,, 2022.
[2] Arora, R. Ge, B. Neyshabur, and Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Leurning, pages 254-263.
PMLR, 2018. 6
[3] Awasthi, N. Frank, and M. Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. In International Conference Machine Learning, pages 431 441. PMLR, 2020. 3.1, 5, C.2, C.3
[4] P. L. Bartlett, O. Bousquet, and S. Mendelson. Localized rademacher complexities. In Compu- tational Learning Theory: 15th Annual Conference on Computational Learning Theory, COLT 2002 Sydney, Australia, July 8-10, 2002 Proceedings 15, pages 44-58. Springer, 2002. 4.3, 29
[5] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013. C.1
[6] Cosentino, F. Zaiter, D. Pei, and Zhu, The search for sparse, robust neural networks. arXiv preprint arXiv: arXiv: 1912.0236,, 2019. 6
[7] J. Dutta, K. Deb, R. Tulshyan, and R. Arora. Approximate KKT points and proximity measure for termination. Journal of Global Optimization, 56(4): 1401--1444-999 1499, 2013. 4.2, 4.2, D.1, 21
[8] N. Golowich, A. Rakhlin, and O. Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299. PMLR, 2018. 3,1, 6, 6, C.I
[9] I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In
International Conference on Learning Representations, 2015. 7, A.1, D, D
[10] F. Graf, S. Zeng, M. Niethammer, and R. Kwitt. On measuring excess capacity in neural networks. arXiv preprint arXiv:2202.08077 2022.
[11] Han, Y. Miao, Z. Sun, and Y. Wei. T-ADAF: Adaptive data augmentation framework for image classification network based on tensor t-product operator. Neurul Processing Letters, 2023.
[12] L. Horesh, E. Newman, M. E. Kilmer, and H. Avron. Generating and managing deep tensor neural networks, Dec. 20 2022. US Patent 11,531,902. 1
[13] Hou, F. Zhang, H. Qiu, J. Wang, Y. Wang, and D. Meng. Robust low-tubal-rank tensor recovery from binary measurements. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021. 5
[14] Z. Huang. X. Li. Y. Ye, and M. Ng. Mr-gen: Multi-relational graph convolutional networks based on generalized tensor product. In IJCAI, volume 20, pages 1258-1264 2020. 1
[15] Y. Idelbayev and M. A. Carreira-Perpinán. Low-rank compression of neural nets: Learning the rank of each layer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8049-8059, 2020. 5

---

[16] Z. Ji and M. Telgarsky. Directional convergence and alignment in deep learning, Advances in Neural Information Processing Systems, 33:17176-17186, 2020. 5, D
[17] E. Kazemi, T. Kerdreux, and L. Wang. Trace-norm adversarial examples. arXiv preprint arXiv:2007.01885, 2020. 3.2
[18] E. Kernfeld, M. Kilmer, and S. Aeron. Tensor-tensor products with invertible linear transforms.
Linear Algebra and its Applications, 485:545-570 570, 2015. 1, 2,1, 2.1, 1, 2.1, 6, 7
[19] M. E. Kilmer, K. Braman, al. Third-order tensors as operators on matrices: A theoretical and computational framework with applications in imaging. SIAM J MATRIX ANAL A, 34(1):148- 172, 2013. 1, 1,2,9
[20] M. E. Kilmer, L. Horesh, H. Avron, and Newman. Tensor-tensor algebra for optimal representation and compression of multiway data. Proceedings of the National Academy of Sciences, 1 :e0128): 118, 2021, 4.3, 4.3, E.2, E.2, F.1, F.1
[21] G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Review, 51()):455- 500, 2009. 2
[22] J. Li, Y. Sun, J. Su, T. Suzuki, and F. Huang. Understanding generalization in deep learning via tensor methods. In International Conference on Artificial Intelligence and Statistics, pages PMLR, 2020. 5
[23] N. Liao, S. Wang, L. Xiang, N. Ye, S. Shao, and P. Chu. Achieving adversarial robustness via sparsity. Machine Learning, pages 1-27, 2022. 6
[24] X. Liu, Aeron, Aggarwal, and X. Wang. Low-tubal-rank tensor completion using alternat- ing minimization. IEEE TIT, 66(3):1714-1737, 2020. 1,5
[25] S. Lotfi, M. Finzi, S. Kapoor, A. Potapezynski, M. Goldblum, and A. G. Wilson. PAC- Bayes compression bounds so tight that they can explain generalization. Advances Neural Information Processing Systems, 35:31459 4414-349334,,, 2022. 6
[26] C. Lu. Transforms based tensor robust pea: Corrupted low-rank tensors recovery via convex optimization. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1145-1152, 2021. 2.1,
[27] C. Lu, J. Feng, W. Liu, Z. Lin, S. Yan, et al. Tensor robust principal component analysis with new tensor nuclear norm. IEEE TPAMI, 2019. 5
[28] C. Lu, X. Peng, and Y. Wei. Low-rank tensor completion with new tensor nuclear norm induced by invertible linear transforms. In CVPR, pages 5996-6004, 2019. 10
[29] B. Ly and Z. Zhu. Implicit bias of adversarial training for deep neural networks. In International Conference on Learning Representations, 2022. 1, 4.2, 4, 4.2, 5, 6, A.2, D, D, D.I
[30] K. Lyu and Li. Gradient descent maximizes the margin of homogeneous neural networks, In International Conference on Learning Representations, 2020. 3.1, 3.1, 4.2, 4.2, 5, A.2, D, D, 19, D.I, 20, 10, D.1, 21, D.2, 11, D.2, 23, 24
[31] A. Madry, A. Makelov, Schmidt, D. Tsipras, and Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
7, D. D,
[32] O. A. Malik, S. Ubaru, L. Horesh, M. E. Kilmer, and H. Avron. Dynamic graph convolutional networks using the tensor M -prrducc. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pages 729-737. SIAM, 2021. 1, 2.2.5
[33] O. L. Mangasarian and Fromovitz. The fritz john necessary optimality conditions in the pres- ence of equality and inequality constraints. Journal of Mathematical Analysis and applications, 17(1)33747, 1967. D.I
[34] Miyato, A. M. Dai, and I. Goodfellow. Adversarial training methods for semi-supervised text classification. In International Conference Learning Representations, 2017. 7, D
12

---

[35] S. Negahban, B. Yu, M. J. Wainwright, and P. K. Ravikumar. A unified framework for high- dimensional analysis of M-estimators with decomposable regularizers. In Proceedings of Advances in Neural Information Processing Systems, pages 1348-1356, 2009. 4
[36] E. Newman, L. Horesh, H. Avron, and M. Kilmer. Stable tensor neural networks for rapid deep learning. arXiv preprint 181.v:1811.00000 1.06669, 2018. 1, 2.2, B.2
[37] B. Neyshabur, R. Tomioka, and N. Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pages 3376-140. PMLR, 2015. 1, 6, C.1
[38] F. Qian, Z. Liu, Y. Wang, S. Liao, S. Pan, and G. Hu. Dtae: Deep tensor autoencoder for 3-D seismic data interpolation. IEEE Transactions Geoscience and Remote Sensing, 60:1-19, 2021.
[39] F. Qian, Z. Liu, Y. Wang, Y. Zhou, and G. Hu. Ground truth-free 3-D seismic random noise attenuation via deep tensor convolutional neural networks in the fime-frequency domain. IEEE Transactions on Geoscience and Remote Sensing, 60:1-17, 2022.
[40] H. Qiu, Y. Wang. S. Tang, D. Meng, and Q. Yao. Fast and provable nonconvex tensor RPCA. In International Conference on Machine Learning, pages 18211-18249. PMLR, 2022. 1,5
[41] D. Savostianova, E. Zangrando, G. Ceruti, and F. Tudisco. Robust low-rank training via approximate orthonormal constraints. arXiv preprint arXiv:2306.014550 2023.
[42] I. Steinwart and A. Christmann. Support vector machines. Springer Science & Business Media, 2008. 4.3, 9, E, 35
[43] Suzuki, H. Abe, and T. Nishimura. Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network. In International Conference on Learning Representations, 2020. 1, 4.3, 5, 6, 27
[44] M. Talagrand. A new look at independence. The Annals of Probability, pages 1-34, 1996. 30
[45] N. Timor, G. Vardi, and O. Shamir. Implicit regularization towards rank minimization in ReLU networks. In The 34th International Conference on Algorithmic Learning Theory, 2023, 4.2,
[46] G. Vardi and O. Shamir. Implicit regularization in ReLU networks with the square loss. In Conference Learning Theory, pages 4224-4258 PMLR, 2021. 4.2,
[47] R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. E, E.1, 31, 32
[48] A. Wang, Z. Jin, and G. Tang. Robust tensor decomposition via t-SVD: Near-optimal statistical guarantee and scalable algorithms. Signal Processing, 167:107319, 2020. A.3
[49] A. Wang, C. Li, Z. Jin, and Q. Zhao. Robust tensor decomposition via orientation invariant tubal nuclear norms. In AAAI, pages 6102-6109, 2020.
[50] A. Wang, G. Zhou, Z. Jin, and Q Zhao. Tensor recovery via *1,sspectral k-support norm. IEEE Journal of Selected Topics in Signal Processing, 15(3):522-534, 2021. 2.1, 2.1, 2.1, 7,5
[51] L. Wang, G. W. Ding, R. Huang, Y. Cao, and Y. C. Lui. Adversarial robustness of pruned neural networks. 2018.
[52] 7.. Wang, J. Dong, X. Liu, and X. Zeng. Low-rank tensor completion by approximating the tensor average rank. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4612-4622 2021. 7
[53] 7. Wu, I.. Shu, 7. Xu, Y. Chang, C. Chen, and 7.. Zheng. Robust tensor graph convolutional networks via t-SVD based graph augmentation. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2090-2099, 2022. 2.2.
[54] D. Xia and M. Yuan. On polynomial time methods for exact low rank tensor completion. arXiv preprint at arXiv:1002.06988) 2017. 3.2
13

---

[55] J. Xiao, Y. Fan, R. Sun, and Z.-Q. Luo. Adversarial Rademacher complexity of deep neural networks, arXiv preprint arXiv:2211.14966, 2022. 1. 3.1, 3.2, 3.2, 5, 6, C.2. C.3
[56] Xiao, Y. Fan, R. Sun, Wang, and Z.-Q. Luo. Stability analysis and generalization bounds of adversarial training. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022. 6
[57] Xiao, R. Sun, and Z.-Q. Luo. PAC-bayesian robust generalization. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
normalized bounds for adversarially
[58] J. Yang, C. Fu, F. Deng, M. Wen, X. Guo, and C. Wan. Toward interpretable graph tensor convolution neural network for code semantics embedding. ACM Transactions on Software Engineering and Methodology, 2023.
[59] D. Yin, R. Kannan, and P. Bartlett. Rademacher complexity for adversarially robust generaliza- tion. In International Conference on Machine Learning, pages 7085-7094. PMLR, 2019. 3.1, 5, 6, 6
[60] X. Zhang and M. K. Ng. Sparse nonnegative tensor factorization and completion with noisy observations. IEEE Transactions on Information Theory, 68( -555)2255 2022. 1,5
[61] X. Zhang and M. K.PP. Ng. Low rank tensor completion with poisson observations. /EEE Transactions Patlern Analysis and Machine Intelligence, 2021."
14

---

Appendix Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networks
In the appendix, we begin by presenting numerical evaluations of our theoretical findings. Subse- quently, we introduce the additional notations and preliminaries related t-SVD, followed by the proofs of the propositions mentioned in the main text.
Our analysis and proofs pertaining to I-NNs differ from those for FNNs follows:
Firstly, unlike the analysis for FNNs generalization bounds based on Rademacher complexity in Refs. [8, 55, 59], we derive specific lemmas for standard and adversarial generalization bounds in t-NNs. This is due to the unique structure of (low-rank) t-product layers. We reformulate the t-product through an operator-liks expression in Lemma 16, paving the way for pivotal Lemma 17, supporting the t-product-based "peeling argument." Additionally, introduce Lemmas 37, 38, and Lemma 33 to handle t-product layer output norms and covering wow-tubal-rank tensors.
Secondly, proving the implicit bias of GF for adversarial training of t-NNs, specifically the approximately transformed low-rankness, is nontrivial in comparison the proof in Ref. [29] for the implicit bias of adversarial training for FNNs. As we consider more general loss functions I-NNs in contrast to the exponential loss FNNs in Ref. [29], we first derive a more general convergence result to the direction of KKT point for t-NNs Lemma 9, and then goes deeper by using a constructive approach to establish the approximately transformed low-rankness in Theorem 10.
Thirdly, differing from Ref. [43] which focuses on standard FNN generalization, our ap- proach delves into t-NNs' adversarial generalization. We achieve this by introducing the (6, r)- parameterization, bounding localized Rademacher complexity for Minkowski in adversarial settings, and using bow-tubal-rank approximations for tensor weights.
Contents
Introduction
2 Notations and Preliminaries
2
2.1 Tensor Singular Value Decomposition
2.2 Neural Networks with t-Product Layer (t-NNs)
Standard and Robust Generalization Bounds for t-NNs
3.1 Standard Generalization for General t-NNs
3.2 Robust Generalization for General t-NNs
4
Transformed Low-rank Parameterization for Robust Generalization
4.1 Robust Generalization with Exact Transformed Low-rank Parameterization
4.2
Implicit Bias of Gradient Flow for Adversarial Training of Over-parameterrized t-NNs
4.3 Robust Generalization with Approximate Transformed Low-rank Parameterization
Related Works
6 Concluding Remarks
10
A Numerical Evaluations of the Theoretical Results
17
15

---

A.1 Effects of Exact Transformed Low-rank Weights on the Adversarial Generalization Gap
17
A.2 Implicit Bias of GF-based Adversarial Training to Approximately Transformed Low- rank Weight Tensors
17
A.3 Additional Regularization for a Better Low-rank Parameterized t-NN
19
Notations and Preliminaries of t-SVD
20
B.1 Notations
20
B.2 Additional Preliminaries of t-SVD
21
Standarad and Adversarial Generalization Bounds for t-NNs
22
C.1 Standarad Generalization Bound for t-NNs
22
C.2 Adversarial Generalization Bound for t-NNs
23
C,3 Generalization Bound under Exact Low-tubal-ramt Parameterization
25
D Implicit bias towards low-rankness in the transformed domain
27
D.I Convergence KKT points of Euclidean norm minimization in direction
29
D.2 Technical Lemmas for Proving Lemma
32
D.3 Proof of Theorem 10
34
Generalization bound approximately low-tubal-rank t-NNs
36
E.1 Several Useful Results
E.2 Adversarial Generalization Gap under Assumption 13
44
Useful Notions and Lemmas
47
F.1 Tools for Analyzing General DNNs
47
F.2 Some Results for Analyzing t-NNs
49
16

---

A Numerical Evaluations of the Theoretical Results
This section presents numerical evaluations for theoretical results. All training process is conducted on n Vidia A100 GPU. For additional information and access to the demo code, please visit the following URL: https: www.uu..cooooooe wwt.ccommmpmm.ee pangzaiwangg/nalyyeaeeeeeee
A.1 Effects of Exact Transformed Low-rank Weights on the Adversarial Generalization Gap
To validate the adversarial generalization bound in Theorem 6, we have conducted experiments on the MNIST dataset to explore the relationship between adversarial generalization gaps (AGP), weight tensor low-rankness, and training sample size. We consider binary classification of 3 and with FSGM [9] attacks of strength 20/255. The t-NN consists of three t-product layers and one FC layer, with weight tensor dimensions of 28 28 28 for ( w(2), and W(S), and 784 for the FC weight w. As an input to the t-NN, each MNIST image of size 28 x 28 is treated as a t-vector of size 28 x 28.
weights ow-rank weights
without ow-renk weights
Anversaria Cenerataaae Sep
C-NN with low-rank waights
2.022
8.000
6.000
0.02
0.08
1.02
snveraral
0.008
2000
2000
0.00
Sam dee siza
1//0
(a)
(b)
Figure 1: The adversarial generalization gaps plotted against the training sample size (N) for t-NNs, both with and without transformed low-rank weight tensors, using the MNIST dataset. In (a), the adversarial generalization gaps are presented against the sample size N, while in (b), they are plotted against I/VN.
Theorem 6 emphasizes: (i) lower weight tensor rank leads to smaller bounds on the adversarial generalization gaps, and (ii) the bound diminishes at rate of O(1 / /N) N increases. We explored this by conducting experiments, controlling the upper bounds of the tubal-rank to 4 and 28 for low and full tubal-rank cases, and systematically increasing the number of training samples.
Fig. I presents the results. The curves indicate that t-NNs with lower rank weight tensors have smaller robust generalization errors. Interestingly, the adversarial generalization errors seem to follow linear relationship with 1/VN: approximately validating the generalization error bound in Theorem 6 by approximating the scaling behavior of the empirical errors.
A.2 Implicit Bias of GF-based Adversarial Training Approximately Transformed Low-rank Weight Tensors
We carried out experiments to confirm two theoretical statements related to the analysis of GF-based adversarial training.
Statement A.2.1 Theorem 10 reveals that, under specific conditions, well-trained t-NNs with highly over-parameterized adversarial training using GF show nearly transformed low-rank parameters.
Statement A.2.2 Lemma 22 asserts that the empirical adversarial risk approaches zero, and the F-norm of the weights grows infinitely as t approaches infinity.
In continuation of the experimental settings in Sec. A. we focus on binary classification on MNIST under FGSM attacks. The t-NN is structured with three t-product layers and one FC layer, with weight dimensions set D 28 28 for ((1), x 28 W(2) and (3)), and 28 for the FC weight w. Our experiments involve setting values of D 128 and 256, respectively, and we track
17

---

the effective rank of each weight tensor, the empirical adversarial risk, and the F-norm of the weights as the number epochs progresses. Since implementing gradient flow with infinitely small step size is impractical in real experiments, we opt for SGD with constant learning rate and batch-size of 80, following the setting on fully connected layers in Ref. [29].
For Statement A. we present preliminary results illustrating the progression of the stable ranks of matrix of tensor weights in Fig. 2 for the settings 1) {128, 256}. Notably,
the MM-block-diagee these results show that the effective ranks decrease as more epochs are executed, thereby confirming the influence of implicit bias on transformed low-rankness, described in Statement A.2.1.
For Statement A.2.2, we present initial numerical findings depicting the progress of the empirical adversarial risk and the F-norm of the weights in Figs. 3 and 4, respectively. These results exhibit consistent pattern with the theoretical descriptions outlined Statement A.2.2 and the numerical results reported in Ref. [29] for adversarial training and Ref. [30] for standard training of FNNs. Specifically, we observe a decreasing trend the empirical risk function and an increasing trend in the weight tensor's F-norm, which align with the expected behavior based on our theoretical framework and corroborate the numerical results presented in Refs. [29, 30].
D-120
D-256
t-product layer
E-product layer
t-product layer
Isproduct layer
Stable weight lerears
E-prdduct layer
Stable rank of woight consors.
E-product layer
100
40
03
20
10000
12000
7500
32500 15000 Epoch
20000
17500
Epoch
(b)
Figure 2: Curves of the stable ranks of the M-block-diagonaa matrix derived from the weight tensors, plotted against epoch numbers, using the MNIST dataset. Two t-NN size settings are showcased: (a) D 128 and (b) D 256.
D-128
D-256
&dverseno empincal mSc
Adversaral empincal rtk
8.008
0.006
8004
0.000
0.000
15000 17520
Epoch
Epoch
(a)
(b)
Figure 3: Curves of the adversarial training loss of t-NNs plotted against epoch numbers, using the MNIST dataset. Two t-NN size settings are showcased: (a) = 128 and (b) D = 256.
18

---

D-128
D-256
1-praduc: layer
6.80
I-produc: layer
945
t-produc: layer
F-lcom of weggtts
0.75
weights
9.40
0.70
6.03
6.60
t-product layer
t:roduct layer
0.33
5.9
I-product layer
2000
5050
8000
10000
22003
2300
5000
7500
20000
21530
15000 17500
Epoch
Epoch
(a)
(b)
Figure 4: Curves of the F-norms of the Miblook-diagonnal matrix derived from the weight tensors, plotted against epoch numbers, using the MNIST dataset. Two t-NN size settings are showcased: (a) D 128 and (b) D 256.
A.3 Additional Regularization for Better Low-rank Parameterized I-NN
natural ask: instead of using adversarial training with GF in highly over-parameterized settings to train approximately transformed low-rank t-NN, is it possible to apply some extra regularizations in training achieve better low-rank parameterization!
Yes, it is possible to apply additional regularizations during training to achieve a better low-rank representation in t-NNs. Instead of relying solely adversarial training with gradient flow in highly over-pare aver-parameterize settings, these extra regularizations can potentially promote and enforce low-rankness the network.
To validate the concern regarding the addition of an extra regularization term, we performed preliminary experiment. In this experiment, incorporated the tubal nuclear norm [48] explicit regularizer to induce low-rankness in the transformed domain. Specifically, we add the tubal nuclear norm regularization to the t-NN with three t-product layer D = 128 in Sec. A.2 with a regularization parameter 0.01, and keep the other settings the same as Sec. A.2. We explore how the stable ranks of tensor weights evolve with the epoch number with/without tubal nuclear norm regularization.
The experimental results are depicted in Fig. 5. According to Fig. 5, it becomes evident that the introduction of the explicit low-rank regularizer significantly enforced low-rankness the transform domain of the weight tensors.
D-128
E-product layer
tepoduct loyer
Stable rank of woightt tencors
b-product leyer
t-product layer 1 (regularized)
product layer (regularized)
product layer 3 (regularized)
20
30
100
120
200
220
200
220
400
Esoch
Figure 5: Curves of the stable ranks of the M-bllock-iagonn matrix of the weight tensors versus the epoch number in the scenario where D 128, both with and without the tubal nuclear norm regularization, using the MNIST dataset.
19

---

B Notations and Preliminaries of t-SVD
B.1 Notations
For simplicity, we use C' etc. to denote constants whose values can vary from line to line. We use We first give the most commonly used notations Table 1.
Table I: List of main notations
Notations for I-SVI)
X E Rdx1xc
t-vector
T E R.xXxx M(-
t-matrix transform via M in Eq. (1)
M Rexe
an orthogonal matrix
t-product
Ty
M-block diagonal matrix of T tensor tubal rank
T.
i-th frontal slice T tensor spectral norm matrix spectral norm
rr(-)
I1-IIF
tensor F-norm
Notations for data representation number channels
C
d
number of features per channel label of multi-channel data X, scale invariant adv. perturbation adv. perturbed version X; radius of (- for adv. attack
X; E RRdxixe
multi-channel example training sample of size N norm used for attack upper bound on ||x||p
y1 (=)
S
6
Ra(-)
X
Notations for network structure
number of t-product layers of a general t-NN weight tensor of 1-th t-product layer with dimensionality di x di-1
W
weight vector of fully connected layer with dimensionality cd2,
f(x: W
a general t-NN with weights W = (W(1) ..... ( w)
Bw
bound on product of Euclidean norms of weights of f E B. i.e. By = B IT B
Notations for model analysis
f(x. v)
adversarial version of fxx which maps (x. inf (s (ef(()
B3
bound on the output of f'x, y) given as B (B, &CR
(x)())
loss function with range [0, B), and Lipstchitz constant Lg (See Assumption 2)
L. L.
standard empirical and population risk, respectively empirical and population risk, respectively
Ludv Ladv
3. Juudy
function class of t-NNs and its adversarial version, respectively
Br, Badv
function class of low-tubal--n
parameterized t-NNs and adversarial version, resp.
Notations for implicit bias analysis (Sec. 4.2)
gi Ams &
example robust, sample robust, and smoothly normalized robust margin, resp.
g.g. bj. bg. K
auxillary functions and constants to chareterize E(-,-) (See Assumption 2)
Notations for the analysis of apprximately transformed low-rank parameterized models (Sec. 4.3)
RN. Rss. Rt
average, empirical, and localized Rademacher complexity, resp.
Ba. gadv
function class of nearly low-tubal-rank parameterized t-NNs and adv. version, resp. empirical Lı-norm sample S and population L2-norm of function f. resp.
[l [
{er J.N
i..dd. Rademacher variables, i.c., E; equals to 1 or -1 with equal probability
20

---

B.2 Additional Preliminaries of t-SVD
We give additional notions and propositions about t-SVD omitted in the main body of the paper.
Definition 6 ((18)). The i-transpose of mRxxxx under the M transform in Eg. (1), denoted by T satisfies
M(T) ),n (M (A)) k= k.,
Definition 7 ([18)). The t-identity tensor E Rmxmxx under M transform in Eq. (1) is the tensor such that each frontal slice of M (I) is a x с identity matrix,i.e.
M I, k= ==
Tad *M T. Given the appropriate dimensions, is trivial to verify that T T -=
Definition 8 ([18)). A tensor Q E Rdddxds is t-orthogonal under M transform in Eq. (1) if
satisfies
Q * Q = Q *M Q
Definition ([19)). A tensor is called f-diagonal if all its frontal slices are diagonal matrices. Definition 10 (Tensor t-spectral norm [28]). The tensor t-spectral norm of any tensor under transform in Eq. (1) is defined as the matrix spectral norm of its M-block-diune bboock-diggona matrix Tar i.e.
TM
Lemma 16. For any I-matrix W E mRXxx and I-vector x E Rnxixe, the 1-product W as X defined under M transform in Eq. (1) is equivalent a linear operator op (W( unfold(X) in the orginal domain defined as follows
op W = (M- & Im) bdiag (M In) I.)) unfold(x). (17)
where & denotes the Kronecker product, and the operations of unfuold and unfold(x) are given explicitly as follows
W
mil
X,1
W
X,1,2
unfold(W)
E Rmcx
unfold(x)
W 1.cc
X 1.c.
Since Eq. (17) a straightforward reformulation the definition of t-product [36, Definition 6.3], the proof is simply omitted.
According to Lemma 16, we have the following remark on the relationship between t-NNs and fully connected neural networks (FNNs).
Remark (Connnection with FNNs). The t-NNs and FNNs can be treated special cases of each other.
(I) When the channel number = and the proposed t-NN predictor Eq. (5) degenerates an (L 1)-layer FNN, which means the FNN is special case of the 1-NN.
= 1, the t-product becomes to standard matrix multi-licatio
(II) On the other hand, by the definition of t-product, the I-NN f(; W) in Eq. (5) has the compounding representation as an FNN:
fw = -wooooooh (()) oo op ((L
(W
Thus, I-NN can also be seen special case of FNN.
21

---

C Standarad and Adversarial Generalization Bounds for t-NNs
C.1 Standarad Generalization Bound for t-NNs
Lemma 17. Consider the ReLU activation. For any t-vector-valued function set H. and any convex and monotonically increasing function g IR (0)
N
1)]
Eg
sup bEH.W: WII
Σ (W MM b(xx))
- 2E
sup g
R
Σ E
((x)))
he?
k=1
where R >>>> O is a constant.
Proof. This lemma is direct corollary of Lemma in Ref. [8] by using Eq. (17).
Proof of Lemma 3. According to Lemma 29, we can upper bound the generalization error of &o f for any f E 8 through the (empirical) Rademacher complexity Rs(L o 3) where l == {lo f f f 8). Further regarding the Lę- Le-Lipschitznes* of the loss function É, we have Rs(E o 3) - L,Rs(3) by the Talagrand's s contraction lemma (Lemmaa 30). Then, it remains to bound Rts (3).
To upper bound Rts (3), we follow the proof of [8, Theorem 1J. By Jensen's 's inequality, the (scaled)
Rademacher complexity N RRs lgg sup E (x,) satisfies
1 π
log exp A Ee sup fEB i=1
Σ e
log Ee sup exp JEB
Σ
(es((x))
(18)
1=1
where À > 0 is an arbitrary parameter. Then, use "peeling" argument [8, 37] as follows.
The Rademacher complexity can be upper bounded as
N (B() = Eg
e, (x,)
sup
( (/,,l /
N W(L)
< log Be
sup
exp
A
e,
*M r (())))((,)
1wl,SBB W(2))
t=1
BB
N
< log Ee
sup R(-1) SB.
exp
Bud
Σ
w(L)
#M
p (xx)
1=1
< log
2. E
sup F 2)
exp
BUB
Σ
w(l-1)
(xx,)
Wil B
i=
p:O) (xx)) (s))
< log
26-1. Eg
sup
exp
B
Bi
Σ
W(1)
(x))
|
S.B
1=2
< log
24 Eg exp
Byp II
Bid
Σ
x
1=1
(19)
Letting Bw Bw I1 Bi, define a random variable
N Σ
Z =
Bw
This is natural consequence of (A.2) in Assumption 2. See Eq. (7).
22

---

as function of random variables (Eih. Then
log (2 Eexp XZ) = Logg
1
log (Eexp A(2 (EE) + EZ.
(20)
X
By Jensen's 's inequlity, EZ can be upper bounded by
N
EZ BwE
Σ
X
Bw
E
Bw
Eg
Σ
(vocv
F
i,j=1
Bw
x F.
To handle the log (E exp A(ZEEZ) term in Eq. (20). note that a deterministic function the i.id random variables {e i, and satisfies
Z Eir 5m) Z -i, Em) S
2Bw ||x
This means that Z satisfies bounded-difference condition, which by the proof of [5, Theorem 6.2). implies that sub-Gaussian, with the variance factor
N
1 - (2Bw |xp1p)2 4
B
llp.
and satisfies
1 12 B Ei
AB
Σ
log (Eexp A22 EZ)) S
X
2
Choosing A
log E
and using the above inequality, we get that Eq. (19) can be upper |
Bw
bounded as follows
log (2t. -Exp & EZ + v 2L 2Bw
X l|
N
(V2L log 2 2 11BB
x
l|p
1=1
Further applying Lemma 29 completes the proof.
C.2 Adversarial Generalization Bound for t-NNs
Proof of Theorem 5. According to Theorem and Eq. (4) in Ref. [3], the adversarial generalization gap of é o for any f E 3 with Li-iiscchiz continuous loss function é satisfying Assumption 2 can be upper bounded by Lę R where Rss (3" is the empirical Rademacher complexity of the adversarial version Jadh of the function set & defined as follows
gady = (f: (x. v) + min
(x(x') |f
(21)
To bound (3 we use the Dudley's ' inequality (Lemma 31) which requires to compute the covering number of g
Let C, be the oy-covering (w()) of I whose t-matrix weights are all in C,:
((()
< Bi}, 1I = 1, ... L. Consider the following subset
3. = [Tc: :6:x Jw. (x) We = (w, (1)), .... W()), w E c.}
23

---

with adversarial version
}
Bady
fa (x.1))
inf vfc(x) Se E 3eJ. naax Yis
For all f E gall, we need to find the smallest distance to Bayy i.e. we need to calculate
|| So
sup inf JEz feE3.
For all (x,.8)) E S, given f and fe with w(O)) w!O òi, 1= L. consider
f(x, yz) - fc(x, vi)1 =
inf
yef(x')
inf yt v.fc(2))
R. 1)
Letting x/ arginn (7(xx-1)) will (x() and x arginf - V/ fe((x), we have
(x vi) (C, 11: -v. ytJe
Let
x if u.f(x() 2 v(f(((
x
if vxf(x)) < vifc(x))
Then,
V.) - fx,, v.)1 = luaf(x)) - vxfo(x))) s lx.f(xx)) - - fx((x))
Let g(()) w voc ((WW! o
(((+1) MM ( (1))))
x²) x")....1)) and g0((x) fo(x)). Then, we have
1f(x5) fo(xf) S (x(( 1x
We can see that
(w *M *M ooW(()))
*M x$) .......)
w('))
xx
II
B B.B
1m1
and
(W(++)
*M (w *M *M (W(())
Sre xf) ..)) o (W(+))
#M o (w *M *M of (W(1)
*M xx) ....).
(((+1) *M o (W(!)
x.x (i)))
w((+1)
(w(() *M o (w(I) * x5² ...))
(Wi(+1) - wll (w
x5)
w((+ w || (o #m
x()).. .....
1-1
< 6, II
By Bz.n.s.
F=1
(22)
Then, we have
(9((x²) 11-1(x 6, Bu II
By Br.
B1
where By is given in Lemma 39.
24

---

&Bi
Letting B,
i. gives
sup inf fe fee
i Falls
(x²)
g -- (xxx) S.
Then, S.th is an e-covering of Budv. We further proceed by computing the c-covering number of gadv follows:
L πI
3Bg
idd-id de
3LBB
El edi
N( :)) S |824
II
C S
81
t=1
i=1
where the second inequality is due to Lemma 32.
Then, we use Dudley's s integral in Lemma 31 to upper bound (3(3)))) as follows
12
D//2
(
<
inf 820
86 +
log N(Fauuly 11-1ls e)de
12
D2/2
inf
88 +
edi log (3LB)/(e))de
820
VN
12D
Σl= edi
11/
inf
86 +
V
Vlog log (3L((2t))
850
N
where the diameter Dj of gady is given in Lemma 40 and we can find from Lemma 40 that Dj 2 in our setting.
Following Ref. [55], let -> 0, and use integration by part, we obtain fo Vlog (3L/(2t))dt s vlog3L 3L. Hence, we have
24 IT Bi (VEia odi- Be,
(s
VN
and the proof can be completed by using Lemma 29.
C.3 Generalization Bound under Exact Low-tubal-rank Parameterization
Proof of Theorem 6. The idea is similar to the proof of Theorem 5. According to Theorem 2 and Eq. (4) in Ref. [3], the adversarial generalization gap of l for any f 3o with L,-Lipschitz continuous loss function satisfying Assumption 2 can be upper bounded by LeRs(( ), where (3 is the empirical Rademacher complexity of the adversarial version gadv of function set 3 defined as follows
3rt := (f (x. v)
min yf(x') Tr).
(23)
R
Raix
To bound (s(d)))) we first use the Dudley's inequality (Lemma 31) and compute the covering number of 3rdd.
Let C, be the d--covering of (w() w
S B, and (W"") rhh VI = 1,... ,. Consider the following subset of 3, whose t-matrix weights are all in C₁:
FF
Fe = {fe:x f(x: W.) W. = (w. w!) ..., w w!O c.}
with adversarial version
Judly : { fo (x.v)
inf vfo(x)) fc E Be
Rx(x-t)
25

---

For all e S," we need to find the smallest distance to Bath i.e. we need to calculate
falls
sup inf JE foc
For all (x,, E S. given and fo with w W S δ1, 111,- L. consider
Vi) - fx(Xx, vi)) = inf
vzf(x)
inf vifc(x)) x)x
[x(x-x)s
Letting x = arginf (x, xEs Ui and x = arginf Rr -1) (x))(x)), we have
[f(x, vi) - Fc(x,,8)) w:)1 | (w: Ja(((x))
Let
if wi((s) 2 (o yx((x)) < (x
Then,
1f(x,)))) v:) Fo(x, vi)l = 1xxf(x)) - yi fo S f(f)) yi y.fo(xfl -1(x)) - -o((x))
Let (0tx((x)) =w - vec (o(W(") *as o (W
* *M (((+1)) *M (M. o (W(())
x²) x))....))) and g0(xx) fx(x)). Then, we have
1f(x5) - fo(x)) S Σ (x( - 1x
We can see that
o ( *M
*M o (W *M xxxx)) xx))....))
II
w (2)
||
S II
B, R.C
1-1
1'=1
and
(W(++) *M (w
*M x ...) (W))
*M o (w
*M o (W *M -.))..)))
*M aM
*M
((++)) o (W(!) *m
....) - w((+1) o (W())
o (W()) xM ...))
(W!(+2) wllt a o(
o ((11) *M xS ......]
w((+1) w (owwi)) *M ((W( #M xf) .....
< 6r II
By Br.
1=1
Then, we have
lx((x() -1-1 6, B
B B2. =
B
&.B,
Letting B:
gives
sup inf feaM feery
1 7 fc <
gi (xx)) -g)1 Sc.
26

---

Then, Seth is an e-covering of ". as follows:
We further proceed by computing the e-covering number of 8.
1.
I.
9
cn(di-+44+1
9LBB
Eis cr(di-1t(+))
N( 11-ll Ball
II
Ci
II
c
1=1
1=1
where the inequality (t) holds due to Lemma 33.
Then, we use Dudley's 's integral to upper bound Rs(3.") as follows
Rs(3r
inf 820
86
12
1112
V /logN(3H I1- ejde
VN
J8
12
D212
inf
86
cri + + 1) log (9LB)/c)de
8>0
VN
12D jV Σi= cri(di- + di +1
1/2
inf 850
88 +
v log (9L/ dt
J/DD,
where the diameter D of gadly is given in Lemma 40 and we have Dj 3. Following Ref. [55].
let 5 + 0, and use interation by part, we obtain fo2 /lo (9L/ Vlog 9L. Further applying
Lemma 29 completes the proof.
D Implicit bias towards low-rankness in the transformed domain
Recent research has shown that GF maximizes the margin of homogeneous networks during standard training, which leads an implicit bias towards margin maximization [16, 30). Moreover, it has been demonstrated that this implicit bias also extends to adversarial margin maximization during adversarial training of mulli-homogeneous fully connected neural networks with exponential loss [29]. Our analysis builds on these findings by showing that this implicit bias also holds for adversarial training of t-NNs when the adversarial perturbation scale invariant [29].
First, it is straightforward to see that any t-NN f E 3 is homogeneous as follows f(x: aW) = a L+1 f(: W),
(24)
for any positive constant a.
Lemma 18 (Euler's theorem on I-NNs). For any I-NV we have
0f(:: W
(L + (x W).
(25)
aw
Proof. By taking derivatives with respect to on both sides of Eq. (24), we obtain @f(x;aW) d(aW) H(aW) da
(L 1))af((fx W),
which immediately results in Eq. (25).
In this section, we follow the setting of Ref. [29] where the adversarial perturbation o, scale invariant. As Lemma 7 shows, F2- [34], FGSM [9], 22DPG and L -PGD [31] perturbations for the t-NNs are all scale invariant.
Proof of Lemma 7. Note that by taking derivatives with respect on both sides of Eq. (24), have
0f(x a W
1+1 (x(x: W
(26)
Ox
0x
Therefore, any 8f is positive homogeneous. Then, for any non Z 8x
(f(x:W) dx
we prove
Lemma 7 in the following cases:
27

---

12-FGM perturbtion [34]. The 12-FGM perturbtion is defined as FGM
Syl'z vlz -Eyz because 8 S Using Eq. (26), we have
FGM (aW) Ey a attzz || Z
SFG (W)
FGSM perturbations [9]. The FGSM perturbtion is taken as δISCM (W) = (sgn(Ey((z) Using Eq. (26), have
PSOM W) Esgn(Ey at [+ = SSSGM (W).
12-PGD perturbation [31]. The 12-PGD perturbtion is taken as
Eyz ||z]|
6 d W (B.().E)
PGD
W
(27)
where j is the attack step, FBy(C) the projector onto 22-norm ball of radius &, and p the learning rate. We prove by induction. For j = 0, we have
|-
Eyal+tz [al+12|lr-
&oD (a F32(0,5)
SPOD (W).
If we have oPoD (aa (aW) =OpOD (W), then for j 1, we have
Eya4+1g
8/th (a)) (R.
(aa((aW)
"|al+tz]] 121F.
Eyz
(28)
(B,(
(W)
Izll
1 (W).
l -GGD perturbation [31]. Since the scale invariance of this pertubation can be proved very similarly that of PPDDD perturbations, we just omit it.
For an original example x,, the margin for its adversarial example x; + 6W) defined as (W) =
fx, + 8, (W); W); for sample S {(x,, ,.) the margin for the N corresponding examples is denoted by 7m (W) where m E argminm=11.- ,N fx + 8, (W) W)
Let p W for simplicity. We use the normalized parameter W W/p to denote the direction of the weights W. We introduce the normalized margin of (x,, y4) as q (W) = q. (W) = q. -(L+1)))),
and similarly define the normalized robust margin of the sample S as @m W = 7m (W) =
Im (LL-).
Note that the adversarial empirical risk can be written as Ladv = EN ((G Motivated by
[30] which uses the LogSumExp function to smoothly approximate the normalized standard margin, we define the smoothed normalized margin 7 as follows.
Definition 11 (Smoothed normalized robust margin). For a loss function satisfying Assumption
the smoothed normalized robust margin is defined as
g (- log
8- (N (a pd+1
g( N
(29)
p++1
"In this paper. the loss function satisfying Assumption 2 belongs to the class of margin- based loss function [42, Definition 2.24]. That is, although the loss function {( (x), y) is a binary function of f(x) and y. there a unary function I(-), such that (x)(x) y) = (()((x). With a slight abuse of notation, we simply use e to
denote 1- (-), i... if ((f(x), y) then have E (-(()) (z) (x))).
28

---

To better understand the relation between the normalized sample robust margin qm and the smoothed normalized robust margin 7, we provide the following lemma. Lemma 19 (Adapted from Lemma A.5 of Ref. [30]). Under Assumption 2, have the following properties about the robust marin qm-
(a) f(ām) log N S log NE f(ām).
(b) Iflog NEw > f(by), then there exists & E (f(îm) log N, f((m)) n (bj, oo) such that im p (1+1) g (E) log N 5 S Qm,
which shows the smoothed normalized margin F is rough approximation of the normalized robust margin Gmn-
(c) For a sequence (W, s E NJ. if Ludv (W + 0, then 17(W,) 9m (W,)) + 0.
D.1 Convergence to KKT points of Euclidean norm minimization in direction
The KKT condition for the optimization problem Eq. (14) are
N
Oq.
W
0,
OW
(30)
(g 1) = O, i 1=
where the dual variables A 0. We define the approximate KKT point in a similar manner to Ref. [29] as follows.
Definition 12 (Approximate KKT points). The (n, appprooxima KKT points of the optimization
problem are those feasible points which satisfy the following two conditions:
N
Oq:
Condition (I):
W
X
S Kr
OW
(31)
t=1
F
Condition (II):
Aı(7: - 1) S 4, i= 1 N
where K. i. and X 2 0.
Proof of Lemma 9. Let W = W/q--- denote the scaled version of W(t) such that the sample robust margin Qm Thus we have W) f W) by homogeneity of t-NNs. According to Lemma 18, we further have
0f(::) W) ) OW
0f(x; W)
(I+1)f(x: W)
W.
(L (L+1)f(X;)) W.
OW
leading to
0f W) W.
0f(x: W)
OW
+/(++1)
OW
4m
We will prove that is (1s, KKT point of Problem (14) with (K, t) + 0.
Let W(t) == aW()) for simplicity. By the chain rule and GF update rule, we have
Oq. ow
W
flo) ((
Using the homogeneity of t-NNs, we obtain
W
W
((::) (a))
ag: w (7:)
(L+1)
Σ e
((5)) ( 7
2
Ww
N
By letting v(1) N e -1(.)) (ee T. we obtain
W, w
1)u/NN
29

---

We construct the dual variables A in Problem (31) in terms of W as follows
(t) = N 4m 21-2/((+1), pe K(::) (( (q:)
W
(32)
To prove W a (K, KKT point of Problem (14), we need to check the conditions in Problem (31).
Step 1: Check Condition (I) of the (x, -)aappoxie KKT conditions. We check the Condition (I) Problem (31) for all to as follows
W
W
W
1/(++1
(/(++11
W
W
W
(1++1
W
4m
(33)
(6)
2 2 2
72/(111)
W
W
(361
2
W
W
((to)2/(L+1)
W
x1)
where equality (i) is obtained by using the definition that W W W/ghtt the fact (.()) fxx + 6, (W); W) = Y: fxx + 6, W) q (W) due to the scale invariance of the adversarial perturbation 5, (W) and the homogeneity of t-NN, and the chain rule in computing 0ū. follows
7W
as
A
0q: W
Oqp OW
(
OW
1=1
4m
N 1=1
W
9m
In Eq. (33), equality (ii) holds by property (b) in Lemma 19; (iii) holds by the non-decreasing property of (t) for all t [to, oo) in Lemma 22.
Note that Eq. (33) indicates that sl) is in terms of the cosine of the angle between (!) and W(I). We can further obtain that x(t) + 0 as + by showing the angle between W(t) and (() approximates 0 which was orignially observed by Ref. [30] for standard training on a fixed training sample S.
Lemma 20 (Adapted from Lemma C.12 in Ref. [30]). Under Assumption 2 and Assumption for i-NNs, the angle between W(t) and W(t) approximates as - oo along the trajectory of adversarial training with scale invariant adversarial pertubations, i.e.,
W(I)
W(I)
lim
1.
WOL
W(t)
F
Note that according to Assumption 8 we have 7(to) > bep(to) ((f(t)))((+))))))) (4++1) which means ((to) cannot be
arbitrarily close to O. Thus, by invoking Lemma 20. we obtain that
lim (t) = lim 1000
1
O.
(34)
t0000 (10)2/(4+1)
W
10eh Lemma C.12 [30] which was intended standard training, can safely extended to adversarial
settings in this paper. This is because by our construction for adversarial training with scale invariant adversarial perturbations, the adversarial traing margin are locally Lipschitz and the prediction function f(x + Ó(W); W) is positively homogeneous with respect W.
30

---

Step 2: Check Condition (II) of the (k, apppooxxiaa KKT conditions. We check the Condition
(II) in Problem (31) for all t to as follows
N
N
(W) - ④
11
pe 1(:) p()))()))))))))))))))))))))
| (ā. (W) - 1)
N Am
(35)
= =||
2/(1+1)
1 (()) pm),
Im
where (i) is due to the definition that W W
W/ and the fact that qi (W) y (x + W W
U: fx, + 5, (W; ; W) q. (W) due the scale invariance of the adversarial pertabation o (W) and the homogenouty of t-NN.
To upper bound Eq- (35), first note that w
W.
W
NN EE e-
0g. aw
W
p (L + 1),/N, in which can be further lower bounded as
(1) g(log NEW
(#i)
((i)) 1
v z g (log Ng
N Lady
2 2K
log
N cadv
e f(0m)) log N
(36)
N
2K
where (i) is due to Lemma 23, (ti) holds because of Lemma 24, and (iii) uses N Liuly = Ei e -((.)) e- -((mm) Combing Eq. (35) and Eq. (36) yields
N
2K mm 2/(++1)
Σ \u 1) 5
((0m))((4))(0 7m)
(L + 1) log NE
1=1
(37)
@ - 11((+11
N
((mm) ((:)) - (m),,
[. 1) log NEW
where (1) uses qT 2/(+11))))
p² S 1-7-/(1++1 by Lemma 19.
In Eq. (37), if q; > gm. then there exists an & (Ām, (:) such that f(ām) - f((.)) = ((() 7m) by the mean value theorem. Further, know that f(())) < K (1.0) (E.) by Assumption 2.
Note that [log2(0. (a./ < ( 4+1 (2 /ūm) S logg (2gg B//7)). where
(C) sup Tpp (L+1)
W + 0) sup (ā: Wi
Then, for all to. we have
2K (((+))( /2
Σ A(( (W) - 1)
K (2oog(2Bo//)
Σ
(m am)
(L 16+11 1) log NEw:
(9)
2Kg-2/ 211++1
K (2Bo/() Ne
(I+ + 1) log NeW
(10 2K 2KNey -2(1-+1))+ 2/(1++1)
Bu 7
(2k)(2K)
(38)
(L + 1) 1)log New
(sic)
2KNe
Bo
(2gg(2K)
1 N Ladv
-log
(L (to) 1/((+11
((4)
:= (t))
where (1) holds because the function x + ²= on o0) has maximum e at z = 1; (ii) is due to log, glos. a; (iii) holds by the non-decreasing property of (t) for all E [to, oo) in Lemma 22. Note that by Lemma 22, we have lim, Ladv (1) = 0, which further yields
lim (()) 0. (
(39)
Step 3: Check the condition for convergence to KKT point. According to Eq. (34) and Eq. (39), the limit point of W(t satisfy the axp.oxape KKT conditions of Problem 14 along the
31

---

trajectory of adversarial training of t-NN with scale invariant adversarial perturbations where lim, (((t)),(t)) 0. Then, we need check the condition between (x, aapproximate points and KKT points.
According to Ref. [30], the KKT condition becomes necessary condition for global optimality of Problem (14) when the Mangasarian-Froma
Constraint Qualification (MFCQ) [33] is satisfied. It straightforward see that Problem (14) satisfies the MFCQ condition, i.e.,
Oq. OW
w
= (L + 1) 2 O.
every feasible point W. Then restating the theorem in Ref. [7] regarding the relation between (x, a)-ppooxiee KKT point and KKT point in our setting yields the following result.
Theorem 21
(Theorem 3.6 in Ref. [7] and Theorem C.4 in Ref. [30]). Let
(W() E NJ be a sequence of feasible point of Problem (14), and W() is a (x(j),(());
approximate KKT point for all j with two sequences"! !1 {x(j) > 0 E N) and {c(i) > 0 -0ijEN JEEN
and jo (K(j), ((())) If limg W(j) W", and MFCQ holds W then W is KKT point of Problem (14).
Recall that W W//gn* Then, it can be concluded that the limit point of (W(t)/ [(t) tt> 0}
of GF for empirical adversarial risk Çadv (W) := N -i=1e f (,,)) (W):W) with scale invariant perturbations is aligned with the direction of a KKT point of Problem (14).
D.2 Technical Lemmas for Proving Lemma
Lemma 22. Under Assumption 2. we have the following statements for GF-based adversarial training in Eq. (13) with scale invariant perturbations:
(I). For a.e. t E (to, oo), the smoothed normalized robust margin 7 (()()) defined in Eq. (29) is con-decreasing, i.e.,
(W(())
2 0.
dt
(I). The adversarial objective Çady (W) pertubations ò, converges to zero as - 00, ie.,
N Ei= fla
Σ N
with scale invariant
lim Cady (W(t)) 1-xx
(40)
and the Euclidean norm of the t-NN weights diverges, i.e.,
lim
W(O) oc.
(41)
Proof of Lemma 22. We follow the idea of Ref. [30] to prove Lemma 22 as follows.
Step 1: Prove Part (I). We prove (I) by showing the following results for all t to.
dlog e dt
and dlog 5
(
dlogp)
W
0
2 (I++1)
dt
dt
dt
Recalling the quantity v(t) EN1
qr by chain rule we obtain
dlog P dp²
1
1
N
Oû: ow
(L++1) (0)
dt 2p² dt =
p²
N
f((:)
(()))
w
p2N 2 0,
where (1) holds due to Lemma 23.
11 UUing the same method to [30, Lemma C,12], we can construct the two sequences, i.e. (k(j) > O EN] and {(()) j N). based on Eq. (33) and Eq. (35).
32

---

By the chaining rule, we also have
dlog
d
log
log
N (
1
- (L+ + 1) log
dl
dl
d'oo
d.V Cudr
(L + 1)2 p(t)
N g(log New
NLadv
dl
p²
1
d. Ludv
(L (1++1) 112 v(t)
v(t)
dt
pe (L (L+ 1)2. u(t)2 p²
d.N Ludy
v(t)
dt
Note that according to Eq. (13), we have
dLadvv
@Ladv
dW
dW
dt
ow
dt
dt
fort 2 0 almost everywhere. One the other hand, we have
dW
Lu(t)
W.
dt
Thus, we obtain dlog
γ
1
dW
dW
dW dt
W
2 Nv(()
[I - vec BeecoW)ver (W)vec(W) Vvec(
dt
Nv
dt
dt
By the chain rule,
dW
dW dt
dt (I
vec ( veee W
\vec(
)
fort 0 allmost everywhere. So, we have
d
0²
dw
( log
-1
dW
2
log
(L 1)
2
dt
Nv(t)
dt
Step 2: Prove Part (II). Motivated by [30, Lemma B.8), we prove (II) as follows. First, note that
dW 2
= p 2 2 (L+1)22
di
di
By lower bounding y with Lemma 23 and replacing p with (g smoothed normalized robust margin of 7 in Eq. (29), we obtain
N 1 )/7) )/9)/((++11 by the definition
dLddvv
I g(lgg Ciar N iunv
2
2/(L+1)
(L (L+1)²
dt.
g'(log NeW
g(log N
gloog
2 2/(1++1)
(I. + 1)3
(N Lulyyy?
g' (log bani )2
where the last inequality holds due to the non-decreasing property of in Part (I). Then, we obtain
g d'(log Now )2
1
2 (L + (1+1) 2((4+1))
g(oog NZ )2 2/(L+1] di N adv
By integrating on both sides from to to t. we obtain
2 (L+ (1+
(42)
No
33

---

where
G(z)= S
g'(logu) u) 1/(N2-0 (ta)) glog u)2 102-2/(L+1) du.
We use proof by contradiction to show the empirical training risk _udvy converges to zero. Note that
(N is non-decreasing. If (Ni does not grow to co, then neither does G( (N
( ). But the
RHS of Eq. (42) grows to oc, which contradiction. Therefore, lim4 N cadv
0. Hence
lim;- Luily (t) = 0 and lim, ptt = cc.
Lemma 23 (Adapted from Lemma B.5 of Ref. [30]). The quantity v = E, e. has lower bound for all 00),
(L)) g(log NEW
N NLaa
(43)
g'(log Ng
Lemma 24 (Lemma D.1 Ref. [30]). For f(-) and g(.) in Assumption 2, we have
g(z)
Yr E [bg. 00) and i(g) (()))
1
E
2Kx 2K
12K 2 Va (o(bg).
g'(x))
D.3 Proof of Theorem 10
Note that the t-NN g(x: V) with weights V (y ,... ,... ((), v) in Theorem 6 has the following structure
8(x: V) v vec(((())
g(x) (x)
(x) E Rmmxllc
g (x) o (V(i) g - (x)) E Rm Vj = 1,...,
g" (1)) =
Let a = B. I and B B,
)- ti, where L is a sufficiently large integer greater than J. We then construct t-NN h(x: H) of L t- p-oduuctt layers which perfectly realizes g(x; V). Specifically, we H h) satisfying the following equation
construct à with weights H H
H L
A
v),
first J t-product layers
last (L-J) J) pproduct layers
or more clearly
(x:: V- VT vecc(h()))
hxx = h (x) E RImXXIXE
h (0 (x) o031 *M (1-1) (x) E RIXXIIe = J + 1,... L
( (x) = la v *M h (x)) E myxic Vj = -1.....J
(x)
where is the t-identity tensor.
easy to prove that for any input x, the input and output of g(x: V) h(x: H), can also be proved that
min yg(x:: V) R
min R
yh(x H)
Therefore, h(x;; H) can also robustly classify (x; y because g(x: V) can robustly classify (x,
Then, we consider the class of over parmterameeerizee I-NNs 3 = [f(xx: W) defined in Eq. (14) with dimensionality of weight (()) E R4xx safisfying di >> maxjss(m;) for all = 1, L.
Specifically, we construct if with weights
w
(wI)
(()) w),
34

---

and structure
f(x: W) w wT veee((((x)
f(x) = (x) E Rdexixe
1 (x) oW!") *M (x) VI =1=1,.. L
p (x) =X. X.
Note that according to our construction there is function f(x: W E & with weights W, (W
L(L) Wh. satisfying
if - m4 S m--1. 5
i S mJ. S m., J + 1..... L
otherwise
and
h: if cm.
W; 0 otherwise
We can also see that (x + 6) = (x + 5) for any x E dgdxixc and any satisfying (, S g. Thus, we can say that the weight W, of f(x: W,) feasible solution to Problem (14), i.c.
min yef(x; + 5 W 2 1, =1==1,11 1. N. R,
Now consider the optimal solution W (W) (L) w to Problem (14). Then according to the optimility of W and the feasibility of W, to Problem 14, we have
w < W < a² B (J 1) + B² (cmJ) (L-
(44)
2(++11
B. LIT
(K + 1 + (cm - J))
and
min yif(x; + 6 W*) 2 1.... R.16,1E
(45)
As there is an example (x".y") satisfying || I in the training set ((x, 1:) S
Idxxix x {+1}. Then according to Eq. (45), we have
f'x(x: W = y" f(x 0: w") 2 min f(x + 6: W R.(8)SE
2 1,
which means
1 f(x))) $
1x |w"
< ||w") 11
W (1)
1=1
2/(L+1)
(,,
||w*|ls
+
(-:() (?)
++1
sp
1=1
indicating that
1
|
1|2
+
Σ
w=
> 1.
++1 1
1=1
sp
On the other hand, according to Eq. (44) and Lemma 25, we have
2d+1
1/2
w (x)))
||
(
B
(K (K+1+ (cm))(
F
Therefore, we obtain
(
L+1
L ++1
1
w
2
w
(1)
2
B
V +J + (cm
35

---

Note that
w(O
W
and
w
W
(1)
M
M
sp
where W M
denotes the M-block-diagonal matrix of weight tensor W Then, have
W
1
I+I
++1
L
(0) M
L
B
(J+1)+
(cm,) L
W
Taking the reciprocal of both sides gives
-1/2
+
E'= Tat (W
(1) M
(1+ t)
+
By
(em))(())](-))
Lemma 25. For every
S i,j
L, we have (+)
W (-)
(1)
||
112.
Proof. Let 1 I i j S L. For J 0. we define t-NN fx V) with weights V (V() VL,v) v) which are constructed from ((x:W") whose weights W (1) (L) w" is an optimal solution to Problem (14). Specifically, the construction of (V(1) vL v) is given as follows:
w
if and 1 }
V
W = 1, L.
if
O if j
Note that for every input example and perturbation 5, fu((X + 5: V) = f(x 5: W then V is also feasible Problem (14). Note that we have
d dy (Iaw-10)
|
2
11] -2
w
-2p -pr /w-
When l the above expression equals (-) ||
Hence, if wr
*
W then the derivative at is non-zero, which leads to a contradiction to the optimality of W Problem (14). Note that if we consider changing norms of (=()) and instead of and W+O) the same conclusion also holds. Thus, the optimality W strictly leads to (+
(+)
W
E
Generalization bound of approximately low-tubal-rante t-NNs
Proof of Theorem 12. Given a (6, -ppproxxximtel low-tubal-rank parameterized t-NN fx: W) e Jo. C Bä.r. let g(x: W,) E 3, be its compressed version whose t-product layer weight tensors have tubal-ranks upper bounded by r.
Step 1: Upper bound the adversarial empirical L, disttancce between and g. Consider function gxx) ( W,) parameterized by W, (1) (L))
rT. w) the function whose t-product
layer weights are low-tubal-rank approximations of ((x; W). Let f(x, y) inf (ufR(x--()) (x')x) and
(xx y) inf (xx) vx(x') denote the adversarial versions of f and g, respectively.
We first bound the adversarial empirical L between f and g as follows.
fx v1) 0(x, v.)l = inf
inf R, -x
Mgg(x))
R,(x, - -E)
36

---

Letting x! arginf (x, -xi Vi (x() and x arginf R. -x)) (x)() we have (f M4)
((x, lux)((x() (x By letting
if fxf(xx)) 2 vi9(x?)
otherwise
we obtain
|f(x,,11 yi) - (X. vi)1 - (xx v.9(X91 S /xx vo((x)) - -10(=11(x)))))))))))))))) s(x5)1
Let hx(x5) = TT vve ((W!!) AM (W *M u ( *M. o (Wi))
x²) xf)...))) and hx((x) = g(xf). Then, we have
(0(x)) g(x5) S
Ihe (xx(x)) 11-1111 (x-)
We can see that for any 1,... L:
lo(w--)) *Ms-
* o(W())
*M x ...... ...))) $ II w
w(C') Ba.R.
and
((ll1))
MM o (W
M x )...... ....) -o((())
*M o (W *M M o (W *M x .....)]]
( *M (W *M (1)
((
*M o (1 *M M a (w *M xii .....
W(C w *ay o (wl11) *M as (1) *M x
(
w
||
(wil-1) *m- o (w #M xx) ...
w
B2,
Thus, we have
8Bj
[x((x)) - 1=-1(x)1 S B
B =
Bi
This gives
4
8B
((x+)) 9(x5))
11(x9) - h 1
B
1=1
1=1
Then, we can set
L 8B,
Σ B
(46)
Step 2: Divide and conquer the adversarial gap. To upper bound the adversarial gap Lady
Čadv (f) of ff by using the properties of its compressed version g, we first decompose the adversarial gap into three terms as follows
(f) [anr(()
(C (ʃ) Ludu (g)) (L Lndy (g)) (Lady
Endy(g))
Andy (g))
(47)
37

---

Step 2.1: Upper bound I.. We first consider the event & in which term II is upper bounded with high probability. As g 8r. the term II has already been upper bounded according to Theorem 6 as
C'L,B1 II <
t
ri(di1 + di) log(9 + 1)) + 3B
(48)
VN
2N
1=1
with high probability 1 - -. Step 2.2: Upper bound I. Note that term I can be written as
Cady (f) Lady (g) (Lady (f) Lady (g))
(ga)(()) -(g())(())))))))))))))))))))))) v) -
(49)
e(
Step (2.2.1): Characterize the concentration behavior of f-o.. Given constant > 0, consider the event (t) in which [ 9 S t already holds with high probability. Then, conditioned on
Lo
Event (t), by using the L--Lipschitz continuity of the loss function ((.,) derived from Assumption 2, it can be proved that ((((x).) E(g(x), y) also has small population L2-norm with high probability.
Regarding Eq. (49). it is natural to characterize the concentration behavior of centered random variable {(f(x), ((r(x), y) - [E((((()) v) {(T(x), v)].
First, its variance under event & can be upper bounded by
var (e(f(x).v) ((T()) -)((())))))) e(Tx)),))
sup || St
Var -()
sup || |5-مlle,
E(x,)) [(([(x,)) - ((x(x,)))) E (( - <()(x mim]
= sup
||ا-ا|
E(g,)) [((F(x v)) E(ī(x, v\)]
< sup
|| ||- St
T [(xx v) o(x.1))
sup
|
L2 $ g /
sup
||-ماl,, St < L7t²
Second, we upper bound its Loo-n First, Lemma 39 indicates that for any E 3 with adversarial version h E gady we have
j 1.2
S B Bw Then, by
3r C 3ar 3. we have | Loc < BB and | L.. B. Therefore, we can upper bound
38

---

((0(x),)) the Lo norm of ((f(x).)) ((((x) Ble(f(x),)) -(](())))))))))))))))))))))))>)) v) as follows
((((x) -((()) v) Ele(f(x), v) - ((T(x)) w)
sup
/ 12 51
[(f(x). ((T(x),))
e(g(x)) + [[((((()) - will
sup
[ 1ffāll all,, St
10c
[(f(x). 9)) ((ō(x), v)
+E ( - ((T(x)) 100
sup
|| | St
sup (u((x) vo(x) + B[Le sup luf(x) vx(x)) (x.))
sup || 1/0=8112 St
(x.1)
sup | f u|l
AL.By.
St
Then, the Talagrand's concentration inequality (Lemmaa 35) yields that with probability at least
1
(Ladl Ludl (g)) (Qudey) (ʃ) Ludl (g))
sup ||
L2 Sr
VLL
BI
S 2
sup || [| St
(Lady (f) L
Ladu(()) (g)) (Cadyy (f) Lody (g))
VN
Then, by the the standard symmetrization argument [47], we obtain an upper bound on term (I) as follows:
E
sup
(Cadee (f) Ludy
(g)) -Ludv(g) (Quuty (f) Lanty (9))
|1--8 St
1 (e(f(x;) v.)) e(o(x,)
(50)
< 22 (N M B
sup ||5- 1 <t
N
where (()) is defined
((t) RN - -oo fe Badr
selt || 8/ S s()
Thus, there is a constant C such that for any j (Sady sedr) satisfying ||| ||r st
holds with probability at least - e-c that
(Cat - (g) (f) Lady (g)) (2)(()) SC ((T)+ Loy + LL
(51)
N
We denote the above event by (t). Note that Event Ea(t) is conditioned Event Ex(t).
Step (2.2.2): Upper bound the probability of Event E2(T) || E||, st). We further bound
-
the probability of Event Et( in which || +|| < r holds. Generally speaking, and are date dependent and we can only bound the empirical Ly-distance between them. However, the local Rademacher complexity characterized by the population L2-norm. Thus, we need to bound the population Ligdistance between and ÿ. Motivated by [43], we use the ratio type empirical process to bound the bound the population L -ddittnnce
39

---

According to Assumption 11, their exists function Ø [0, oo) - [0, oo) such that
Re (Batr 3r S (tr) and ((2t) S 26(T), (Vr > 0).
Define the quantity r(r) = E sups (+ Ei=l Ex 3:) h E (3 3. : || L2 s sr)
Then, we have
r(t)
E
sup
1
hy X wi)
(Barr sea)) ): ||tell |
N
Egh(x; 31) h E (Barr sze)) 110lles Sr $1
2B
E
sup
N
(4) S 2B (
2B RR
37
where (i) by the Talagrand's contraction lemma (Lemma 30). We can verify that the square (-) of any function E B Br satisfies
(i) its T norm is upper bouned by B3, i.e., || 1. (KP() (x² S B3.
(ii) its second-order moment satisfies Exp [(h2(x,))) y)
S Exs (2((1(xx
By [x]
Thus, h²2 satisfy the conditions in Eq. (7.6) and Eq. (7.7) of [42] with parameters B B3 V = 133 and 0 = 1. Noting that we have upper bounded ((t) by 2 then by the peeling trick [42, (Bady
Eq. (7.17)], we can show for any t in / h
sal") : 11/111z, S r] and > that
1MlE, - ||Al ||all +
2B BB po(t)
2t
2t
P
sup hE
8
22
+ Biy
2
B²
22N
se
31
We further define a function E, = (t) as
16B (
2t
1
(t) == inf r
B Biy
+
B
- 2
(52)
22
PN
F
which useful to bound the ratio of the empirical Iz-norm and the population I2-norm of an elements h Jady gadv with probability at least 1 - el:
-e!:
| |1 ||A112_ + r
IMME S 2(114 + +²
2
+
Recalling that | is at least 1 - et
-
< i, we obtain that the probability of Event Et(t) with i t=
Step 2.3:
Combining Events (t), (t). By combining Eqs. (46), (47), (51) and (48) along with
their underlying events ε,, Ea(t),a((t) we obtain
CLLBB VN
L (a))(() (adu(1) (
ri(di- + log + 1)) + B
2N
tLeBr
+ C2
((i) + Let
+
N
N
with probability at least -
40

---

E.1 Several Useful Results
According Theorem 12, it remains to upper bound @(t). In this subsection, we derive upper bounds on Φ(r) in terms of covering numbers of the considered function sets B. and Bar
Consider the supremum of the empirical Lo-norm of any function (f- g) E (3 3rth) ) on sample = ((x,,,))) 1i) when the population Lz-norm is bounded by given radius t > 0 as follows
Bs = Bs(() - sup {
|| o|
| -
La S f E 8ar 9 E 3
(53)
Recall that we have assumed (3%% ) S Φ(T).
We now give explict example of ø(t) in
terms of the sum of covering entropy of Bär and B
Re selr)
Es Re (f(F- (g- E (S
8/ 102 sx))
log (fUF-D) g)
(B :ppt), ;
|| 9 La
$t))
(1)
inf
+ Es
dc
N
log N ((vi-) 5) E gaddy
Frdv), ||
5
st))
-1-Ills
(186)
As
Ln
Eg
de
N
I/N
N
(6n)
log N(Bar I1-Ilss c/2) + log N(8ph)
11-Ils c/2)
+
E
de
N
N
1/N
d(t),
(54)
where (i) is the definition localized Rademacher complexity; (ii) is due to Dudley's s inequality (Lemma 31); (iii) is obtained by letting 1/N; (iv) holds by Lemma 34.
Lemma 26. can upper bound ((r) by using Φ(t) as follows
((t) I CLeb(T).
(55)
Proof. Recall that (()) is the average Rademacher complexity of the function set
{ ( - tog
S r, f E B E 3
As E(-) is Le-Lipschitz, we have for any functions j E sady . E 3rdh satisfying | St
lo f - lo 9
Σ
N (e(f(x, v.) ((0(x;,))))
sup f.g
sup
f.g
N [T(((())V))) O(x,, ((x...:))
sup f.
N (f(x.V) 5(xx wi)
sup Le
f.j
1=1
LL sup f.g
LeBs.
41

---

where (1) holds because the loss function é is Le-Lischitz continous. To bound (t), first bound the its empirical version using the Dudley's inequlity (Lemma 31) up to constant as follows
log N [ j Bor y E Bp
| - 3| L2
St)
cheBs
inf
+
de
e>0
N
logN (Lof-lon fogiee gadv I E srcy ||
8
0 Laz
srl)
(
Le N
de
LIIN
N
(f- f E Bal I E Baey | - 5/
log N
5t}
,//llss,//L)))
Le
de
N
Le/N
log N (f- f Badd
Baiy
| f- - L12
<t}
.l.-ls.tt)
(116)
Tu
As
$
L,dt
1/N
= Leo(t).
(56)
where in (i) we let a = Le/N; (ii) holds by the Lipschitzness of l and the definition of covering number; we use change of variable L/ in (iit).
By taking expectations on the RHS of Eq. (56) with respect to the sample 8, we obtain Eq. (55).
To determine appropriate radius of the population L2-norm i == 2/ r2. need to compute the value of t, of satisfying Eq. (52). Using Eq. (54), we show how to compute o(t) when the covering numbers of 3adv and 3 satisfy special bound.
Lemma 27 (Adapted from Lemma in Ref. [43]). Suppose that the covering numbers of 3 and gauly satisfy
sup log N(3 s
sup log N(3. .l-lll. S a1 + a2 log(e-1) + age aze-24
(57)
s
for some q < 1. Then, it holds that
(I) The bound Φ(T) of the local Rademacher complexity Re Re upper bounded as
selv) of radius t can be
1
+
log N
01 + a2 log
N N
((t) & C max
BB
+ry
+
N
N
(58)
Bl-
C
+
T+V
1-
43
N
N
for a universal constant C > 0 and a constant C, > 0 which only depends on S 1.
(II) In particular, the quantity (t) satisying Eq. (52) can be upper bounded
(t)t) < B a: + as log N
a3
1
B
Ly
149
+ +1)
1 1 tB
N
N
N
42

---

Proof of Lemma 27. According to Eq. (54) which gives o(t) and the definition of 3s in Eq. (53), we need upper bound
As
log N(
|llls, + log N(3r"t 1 de
Es
I/N
N
a1 + 02 (02log((=)))) + age 2q
S Es
de
I/N
Bg
01 + 02 log(e-1)
As
03 24
$ Es
de + Es
de
1/N
N
1/N
N
Va3
41 + a log N BsBs + 1 Esgs 1
V 01 + 02 log N 2B gob(( + + +
Vaz
2B (0(()) +1²)
1
Hence, if 2 II, then
1 N
01 + 02 log
Φ(t) <
+
N + v 2B fB((( + +
C
a1 + 02
l2g
N
a1 + a2 log N
Φ(t)
C²B,
+ +Cr
N
N
2
which leads
2C N
01 + az log N
a1 + a2 log N
(tt) S + 20 Bj
+ 2Cr
N
N
If I II, then by using Young's inequality we obtain
((t) C
N +
/03 1-9
(2B (2Br
+
+
C + 9
C²
N(1 -
NN1-9)² q)²
+ +(1 9)
2B (o(()
Ci
N(1 4
03
2 9)
for any > 0. Thus, by taking = 4C(1 - 9) Bi. we obtain
((t) <
2C
CgC
(4C(1- - B)) ())
+20 20
a3
2
N
N(1 - -2)
N(1 9)
1-3
B a3
144
2C
2q0² .474
2C
r! (1-9) -)
03
N
1-9 1
(1 ②)
N
B3 903
C
Cg
Cyr(1-o)
a3
N
N
N
where C. > 0 a universal constant only depending on
Then, we obtain the bound on ((t) in Eq. (58). The bound on e can be obtained by simple calculations based on Eqs. (52) and (58).
Lemma 28. When the population L2-norm of any function h f - g E (3 - F.udy) is upper bounded by t, its squared empirical Lz-norm can be upper bouned as follows:
N
E.
sup
1xx,, 31 h E (B sadv) and ||All 5t)
< 2B R.
B.. + 2.
(59)
43

---

Proof. The squared empirical L2 -n-no can be upper bouned based on the population L2- Ln-norm as follows
N
(8% )r and || L2 str) ]
1
Es
sup
h(,, bi)
N
==1
E
sup
Σ 1(x,, vx);+1))²
( y) h E (B8r ) and ||A|| st)
+
(4)
N
S 2B5..
sup
Σ e,h( v:)
(3ar 3. and |Plllzz r
+ +
(10
N e (x, 9i) h (Bar - se 11lll S
< 2BrBs,
sup
+ +
2B (8
+
- 2B x2Boo(t) (())
(60)
where (i) is due the symmertrization argument [47] and { are i.i.d. Rademacher variables, and (ii) holds because of the contraction inequality (Lemma 30).
E.2 Adversarial Generalization Gap under Assumption 13
Proof of Theorem 14. In this situation, we that for any 1 S 71 S min di-1), 1), we can approximate ( with its optimal tubal-rank-ri approximation tensor ( according [20, Theorem 3.7] and achieve the following approximation error bound on F-norm
(1)
(
X3 M ((()
X3 M
F
F
minfdl d
(W(()) X3 M)...k
jmrr+1
c minfdi di-1
(Vo j-a j=r+t1
Vi2 1)1-2a
2a
Vorl (1-(1_2))/2 == 8P.
2a
where (i) holds because of Lemma 41.
We also have a specral norm bound for (()) w according to [20, Theorem 3.7] under Assumption
13 as follows
(
W(O) sp
S Voln + " 6%.
and we also have
VeSgD < 6F.
(61)
W(L) w) the func- tion whose t-product layer weights are low-tubal-rank approximations of (x; Let f(x, v) = inf (x(x') and g(x. y) inf infx(x-x)s xx(x') denote the adversarial versions of f and g. respectively.
Consider function (x) g(x: W.) parameterized by W. (W
This helps us bounding i follows [f(x, v1) 5(x, v.)l = inf
vif(x) inf
3gg(x))
R, R -E)
R. -
44

---

Letting x! arginf (x, -xi Vif (x() and x = arginf Rx -xx) Bx)(((), we have (f M4)
0(x,,36) lux)(xx() - (x By letting
if vr((xs) 2 vo)(x))
otherwise
we obtain
|f(x, vi) - (8x, vi)1 = (x)) v.9(X) S (( v. = 1f(x)) g(x5)).
Let Let = wTvec ((W(L) *M
*M (((+1)
*M (W() .M. *M.............................. *M a (W))) AM
x xf)...)))) and ho(x5) = g(x²). Then, we have
1f(x5) - g(xx) - Σ
(xx(x)) - 1x-1(x))
1=1
We that for any 1 1,... L:
(W(l-1)) *as
*M o (W(1) x (....))
w((')
Ba.
1=1
p=1
and
(w()) ri *as (W(l-1)
*M *M (W(1-1)
#M xx) ..... (W(() *M o (w *M
*M (W(() *Ms xx)....)
( *M (w(1-1)
#M xSx ...) w *M (W #M ... *M ow *M xf) ...)
( w(')) *as
x ....) ||r
w w (w *M
(1))) *M x)) ..)...))
$ 6,90 II w(r)
Be.R.E.
where in (i) relax the inequality by using the tensor spectral norm of insted of the F-norm of w! w(O which leads to a smaller upper bound. Thus, have
8 B
(xx(5)) 11 B II B B2, R.S
Bi
This gives
1
1. 8.8 Bj
lf(xf) g(x{)1 $
hx((x)) - 1x-1
<
Br
[m]
Then, we can set
6 Bj voBB (ri + 1)
(62)
B
Br
Then we can construct an e-cover of Ball composed of 5(x: W,) by carefully setting the value of rank parameter (r1, ,TL) according the covering accuracy Directily setting 6 DJ 2B:
e/L,
we obtain
r ==min
min {[ A 1T
1, di.,dd-1) s min { ( ,d, d
where
B
A: =
LVV.B
45

---

Then, we obtain the covering entropy of B by
1.
rd(+td-++tee
9B
log N( .) S log II
of
i=1 L
rdd+d 1+1)e
9B;
log
II
VC
1=1
(63)
ri(ch dj-1 1)clog(99.B/((Vc)))
$ Σ (AIC ) + + + 1)c (1g(c")++
where (ii) holds by Eq. (61).
Since Br C 3ör we have
log N( Il-lls c) log N(3 11-lls c) s Σ ri(d + d:1 + ()clog(9LBB/((cce)
To use Lemma 27, we bound log N(3 I1- , e/2) N(3.") [ells:E/2/ when 2 2/N follows:
log N(
+ N( llllls. c/2) s an + as log(c + azc
where
a1 log(9oB /VCja2,
02 r(d + dj-1 + 1),
1 Σ
log + log(9LB///V))
Ar + d:-1 + 1).
1=1
For simplicity, further let
E a1 + 02 log N.
c L
rids + d + 1)
1og(9NLB//Ve),
N
N
(64)
E2 ag C
Ac(di + di-1 + 1)
log(9NLB;/VC).
N
Then, according to Lemma 27, we have
=0 C B2L
(t)
1+ tB;
2u
B3 +1 +1}
20-1
}
(65)
which further leads to
1LeB
+(t) L,t N
tL
< (l) + 2te(t + +..)
N + N
(66)
(1
1
C,L,max
+ BBEEi + (t+
E 2
+ 2ull
(f+ v.)
JuTF
E2
N
t
tLeB;
+ +t
+
N
N
Note that
= i SVE, + 1 1. +
1 E,
2 2
46

---

+ t. sa
20
v Eg S faat] v Eng + x
2n
20+1
v En.
( (++ N
VV N
1 +
Then by simple calculation, we have
t
LL
((t)
Lot
N
N
2
1+ ++B
I Cate Bi + +-V E
E2
B
20
+1) E2 +
+
N
Proof of Corollary 15. The bound in Corollary 15 can be directly obtained if we choose the parameter of tubal ranks in 3r by ri , 1)01,, d1,d)-).
Useful Notions and Lemmas
In this section, we provide several notions and lemmas which are used in the previous analysis.
F1 Tools for Analyzing General DNNs
We briefly list the tools used in this paper for analyzing the generalization error of general DNNs, including Rademacher complexity, covering number, and concentration inequalities, etc..
Definition 13 (Rademacher complexity). Given an i.i.d. sample S == ((x, y:)l of size N and a function class H. the empirical Rademacher complexity of H is defined
1 E,h(x,,,
Rs(H)) = BEi EN
sup kiEH N
where E....., .EN are ii.dd Rademacher variables, i.e., E, equals to or -1 with equal probability. The average Rademacher complexity is further defined as
RN EsRs(H)..
Lemma 29 ([4]). Given an i.i.d. sample S = {(x,, vc) W of size N, a loss function E(h(-), v) taking values [0, B), the generalization error of any function J in hypothexis set satisfies
C(f) s (()) (2 o) 3B
(67)
2N
with probability at least 1- -t for all 2.0 0.
Lemma 30 (Talagrand's contraction lemma [44]). Given function set F and Lisscctt, & F}. we have
for a function sets defined as LF == {fo
RT(F) < (F).
Definition 14 (e-covering net). Let 0 and (X, d((--)) be metric space, where d(-..) is (pseudo)-mett metric. We say C X an c-covering net of X, for any x E X, there exists E such that d(x, 2) & Define the smallest [2] the e-covering number of X and denote N(X, d(; c).
Given a traning dataset 5 = [x J. and function set F. Consider the output space of the space of F restricted on S, i.c. Fls = {f((x) v1), ... (()x)N)) [ e F}. Then, define a pseudo-norm of Fis as:|| N V f(x, 22 Then, the Rademacher complexity of F could be upper bounded by the e-covering number of F under the empirical 1o le-pseudo-metric by the Dudley's 's inequality as follows:
47

---

Lemma 31 (Dudley's ss integral inequality [47]).
The Rademacher complexity Rs(F) satisfies
12
m liflls
Rs(F) S inf 4
86
log N(F, 11- c)de
(68)
VN
Lemma 32 (Covering number of norm balls [47]). Let B be a l--norm ball with radius W. Let d()),x)) = [X| xel1p Define the e-covering number of B as N(B, d(.,)).c), we have
2W
N(B, d(. ((.))))) -
(69)
Lemma 33 (Covering number of low-tubal-rank tensors). For the set of tensors T, := {T E Rmxxxc [T) r. || S 13 with r I min n), its c-covering number can be upper bounded by
9
(m+++ 1)re
7, e) S
(70)
Proof. Consider the reduced I-SVD [20] of tensor X U V E ET,, where *M denotes the t- t-product induced by the linear transform (-) defined in Eq. (1), U e mmxxxc and V E Raxrxe are (e-mi))--rtthogonm tensors, and S E Rexrxe is an f-diagonal tensor. As T E T,, we have The idea is to cover T, by covering the set of factor tensors U, V and
X S
Let D grxrxe be the set of f-diagonal tensors with F-norm equal one. We take D to be an e/3-covering net for D. Then by Lemma 32, we have |D| I (9/e)"5. Next, let Om,r { Rmxxxc
U KM U = !]. To cover O m.r. we consider the 11 defined as
X 2, == max II
22.2. $ 1}. Then, we have mm, C Qi,r by the definition of orthogonal tensors. Letting m be an e/ e/3-covering net of Qm.r. then we obtain QQ S (9/e)mre by Theorem 32. Similarly, an e/ e/3-covering net of Qn.r satisfies Q S (9/e)arc.
Let Qm. == (X E R XXXXX
Now construct a set T {U" S * M
m.r S D., V. (. Then, we have Q I (0/c)(mn+11)))
T = Q
|
Net, we will show that T. is an e-ooerrngg net of T,, i.e., for any X E T,,, there is an X E т satisfying X X S.
Given E T,, consider its reduced t-SVD as X = U S * V E T,.. Then, there exists
X U *M S *M (V") with U Q o S D v Q satisying | - U 2,,22 $ c/3,
IS l I e/3, and V ve V 2l,,,,2 S E/3. This gives
X X
U U S HM V U H S AM (V
U S KM V U * S S*M
M V
& S *
V
M
*M
M K V
U
* S NM T
U
MM
M
MM S W
+ U *r S
*
S
(V
M xM V U *M*M>
S M y
+
U
#
MM
5
M
+ U *M
S
*M v
*a S M V
< 09) *M *M V +
U PM (S (o)
*M
+
U
*M
S *M (V
Vo T
||
48

---

For the first term, note that since V is a t-orthogonal tensor,
(U (U- - U + S*
= II(U - U9) *M Sl
F
and
[ - 09) * S
U Dia *M S.til
[
I li
S IP max |I D...F
S f 20,2,
(e/3)²
Hence,
(U - U9) aM S m V
S e/3. Similarly, we have U *M S *M (V - -V- S c/3.
The middle term can be bounded U (S - 5 *M V
S ||S S I c/3 due to the
property of t-orthognal tensors U and V [20]. Therefore, for any X E T,, there is an X T
satisfying X X c.
Lemma 34 (Covering number bounds for composition and addtion [10]. Let Fi and F2 be classes functions on normed space (X, l+lxx + (2, (1-yl- and let F be a class of f-Lipschitrfunctionss functions (22, 1--y)- + (z, 1-112) Then for any X X and EF, EF > 0, it holds that l1-lxx) - N(FI, + + F2her
and
N(I WllfofifEER Fileer cEs, |1lx = N(FI lk sup S.F
Specifically, iF {S} is a singleton, we have
o E
< N(File
Lemma 35 (Simplifided Talagrand's concentration inequality [42]). Let F be a function class on X that is separable with respect to Lic-norm and {x,),1 be i.i.d. random variables in X. Furthermore, suppose there exist constants V and U 2 0 such that V supjer [E[[ ][
and U supser IIfllr. Letting Z suP IN E f(x.) IE[f]]. then it holds for all t that
2VE N
211
P
2 2E +
+
Se_t.
N
F.2 Some Results for Analyzing t-NNs
In this subsection, we present several fundamental statements described lemmas for analyzing I-NNs. First, we give Lemmas 36-38, which are used in the analysis of the t-product layers.
Lemma 36. Let (()) RR -
R be Lip-iipshit function, funnciiittfunntiion ie., (a(x)) a < I. | vl. Vx, E IR.
If it is applied element-wisely to any two real vectors x and y, then it holds that
|lo(x) - -oy)) < Lo I|x yll,.-
Lemma 37. The following inequalities hold:
T
and
[ M x|| < W |x|||- <
| |x/pp
Proof. According to the definition of the M transform in Eq. (1) and the orthogonality of M, we have
T
T
<
TM
[| ||T||
49

---

and
(1)
[ #M x
WM M
XM
Wa M
|| 1I
[|
sp |x||=
[ ||
F
where inequality (i) holds because dimensions.
|
||||] | for any matrices A, B with appropriate
Lemma 38 (The 1-product layer is Lipschitz continuous). Suppose the activation function is Lo Lipschitz, then layer of 1-product layer h(x) = ( *M X) is at most Lo [ Liisccittt
Proof. According to the Lipschitzness of the activation function, we have
[ - 1(xx = ||o
W
*M X1 a (W *M X2)
Lar
W
*M X1
W *M Xellr
La
*M (X1 x2)
L
W
| -X21F-
We then present Lemma 39 and Lemma 40 which are used in upper bounding the input and output of I-NNs adversarial settings.
Lemma 39. Given a fixed example TR.x 1xc if an adversary x' satisfies Ra(x x') S &, then holds that
x Elle S Br + ECR.
Lemma 40. The Lose norm of any f(x: W) Jauly defined on the set of input examples X is upper bounded by
|
sup fe
S BB:=
By B2.R..
(71)
L.w
The diameter of Bady is can be upper bounded as follows
[
Dj 2 sup
S 2Bw
(72)
Jegu
Proof. For any E given example (x E EX x (=13 let x" E (x- (x() be one adversarial example. Then, we have
( v)l
inf 1x)((') (i-
If(x))
w T voo (x"))
||w/|
(x))) F
|
(0))
(x*
L
w
Bi
(x')
B
Bi ByB BR.E
R
Bj:
50

---

which also implies
|
II B.Be.Ra.E.
Dj = max fe
s 2B
Lemma 41 helps upper bounding the F-norm residuals after low-tubal-rank approximation of the weight tensors of t-NNs under Assumption 13.
Lemma 41. Given constants a > 0, > 1, suppose a sequence (2y)5=1 satisfying polynomial decay
Zj S oj, then for any positive integer n, we have
Σ
an
2
Proof. We compute the sum of the sequence using integration follows:
Σ 2
S
at
dt
a
Jon
51


Reviews:
[{"review_id": "lQc3lAiMEi", "reviewer": "Reviewer_EpHo", "summary": "The paper studies the generalization error in the standard and the adversarial settings of t-NNs, neural networks with layers and features parametrized via t-vectors and t-products.\n", "questions": "- the authors should clarify in the main text how the obtained results differentiate with respect the corresponding bounds for linear fully connected nets (for example the bound in Thm 6 and Thm 10) and should highlight what the main differences in the proof/analysis of these bounds are with respect to the linear case\n\n- I think the rank-adaptive approach for selecting the ranks of the network mentioned on line 186 deserves more attention - in particular, i do not really understand in what way rank-adaptivity can be exploited in the analysis provided by Thm 6. See also [x],[y] for alternative recent rank-adaptive strategies for linear layers.\n\n- The fact that adversarial training leads to low-rank weights and vice-versa reducing parameters has a positive/negative effect of robustness (as mentioned at line 250) is subject to ongoing active research and there is a variety of different observations/results on this subject (see eg [a-d]). I would rephrase here in the light of these papers. In any case, these empirical studies are done for networks in the standard form not for t-NNs. Using that evidence to comment on findings for t-NN seems to support my weakness no. 1\n\n[x] H. Yang, M. Tang, W. Wen, F. Yan, D. Hu, A. Li, H. Li, and Y. Chen. Learning low-rank deep neural networks via singular vector orthogonality regularization and singular value sparsification (IEEE/CVF 2020)  \n[y] S. Schotthöfer, E. Zangrando, J. Kusch, G. Ceruti, and F. Tudisco. Low-rank lottery tickets: finding efficient low-rank neural networks via matrix differential equations (NeurIPS 2022)   \n[a] https://openreview.net/pdf?id=SJGrAisIz\n[b] https://arxiv.org/abs/1912.02386\n[c] https://arxiv.org/abs/2306.01485\n[d] https://link.springer.com/content/pdf/10.1007/s10994-021-06049-9.pdf?pdf=button", "limitations": "The authors have added a \"limitations\" paragraph stating that the obtained generalization bounds may be somewhat conservative, which I agree with. I am not sure I understand the proposed solution to the limitations though.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The provided generalization bounds for t-NNs show that neural networks with low-rank parameters have the potential for a better generalization.\n- This type of generalization analysis for tNNs seems new", "weaknesses": "1. Although I appreciate this type of analysis for t-NN did not appear before, the t-product is essentially a composition of operations obtained through a suitable block reshaping of the parameter kernel, thus extending the results from standard fully connected linear layers seems like a natural and relatively direct result. In light of this, the novelty of this paper seems limited\n\n2. I would have liked to see a few numerical experiments validating the theoretical findings and the tightness of upper bounds -- also to address the claimed limitations at the end of the paper\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1** (Novelty).\n\n**Re:** We appreciate the reviewer for acknowledging the novelty of our analysis for t-NNs. We believe that our analysis can bridge the gap from the existing applications to a more rigorous understanding of t-NNs in machine learning. Notably, t-product's distinction from linear products in traditional FNNs underscores their structural and algebraic dissimilarity. This forms the basis for our unique approach and sets our analysis apart from FNNs.\n\nSpecifically, the unique structure of t-NNs, including their t-product and transformed low-rankness, precludes the direct adaptation of generalization bound proofs (e.g., Lemma 3 and Thm 6) from [5, 42, 43], designed for FNNs. To address this, we derive several lemmas tailored to the special characteristics of t-NNs. For instance, Lemma 3 involves a t-product-based \"peeling argument,\" implemented by reshaping weight tensors using Lemma 16. This sets the foundation for the crucial Lemma 17, supporting the argument. Furthermore, the proofs of Thm 6 require control over t-product layer outputs and the covering number of low-tubal-rank tensors, achieved through Lemmas 37 and 38, and Lemma 33, respectively.\n\nLikewise, proofs for adversarial generalization bounds for t-NNs with approximate transformed low-rank parameterization can't straightforwardly stem from the analysis of [34] for standard generalization of FNNs. Challenges arise due to capacity control mismatches under adversarial attacks on t-NNs. To address this, our proof involves introducing $(\\delta, r)$-approximate low-tubal-rank parameterization for capacity measurement, controlling localized Rademacher complexity of the Minkowski difference of adversarial-counter parts of two t-NN classes for Thm 12, and employing low-tubal-rank approximations for precise capacity control in Thm 14.\n\n**W2** (Numerical experiments).\n\n**Re:** Please review the initial numerical evaluations in rebuttal \"Contributions and Numerical Evaluations\".\n\n**Q1** (Differences of results, proof, analysis of the bounds from FNNs).\n\n**Re:**\nOur theoretical results significantly differ from corresponding FNN bounds:\n\n- The standard (resp. adversarial) generalization bound in Lemma 3 (resp. Thm 5) differs from the counterpart for FNNs [5] (resp. [42,43]) due to the role of the channel number $\\mathsf{c}$ in t-NNs' parameter complexity. Additionally, Thm 5's bound covers broader adversary classes compared to $l_p$-attacks in [42, 43].\n- Thm 6's notable divergence from [42, 43] lies in its inclusion of weight low-rankness in the adversarial generalization bound. This aspect hints at the potential for enhanced robustness in generalization.\n- We introduce a novel concept in our analysis of GF for adversarial training (AT): the implicit bias of approximately transformed low-rankness in t-NNs. This significantly extends and enhances the findings from implicit bias in AT for FNNs in [22], which concentrates solely on convergence to a KKT point with exponential loss. Our research goes further by investigating approximately transformed low-rankness for t-NNs with broader loss functions in AT.\n- The key distinction in the adversarial generalization bounds of Section 4.3 from non-adversarial bounds for FNNs in [34] is the inclusion of the localized Rademacher complexity of the Minkowski difference between adversarial-counter parts of approximately and exactly low-tubal-rank t-NNs in Thm 12.\n\nOur analysis and proofs diverge from linear cases:\n\n- Unlike the analysis for FNNs' generalization bounds based on Rademacher complexity in [5, 42, 43], we derive specific lemmas for standard and adversarial generalization bounds in t-NNs. This is due to the unique structure of (low-rank) t-product layers. We reformulate the t-product through an operator-like expression in Lemma 16, paving the way for pivotal Lemma 17, supporting the t-product-based \"peeling argument.\" Additionally, we introduce Lemmas 37, 38, and Lemma 33 to handle t-product layer output norms and covering low-tubal-rank tensors.\n- Proving the implicit bias of GF for AT of t-NNs in Thm 10, specifically the approximately transformed low-rankness, is nontrivial in comparison to the proof in [22] for the implicit bias of adversarial training for FNNs. As we consider more general loss functions for t-NNs in contrast to the exponential loss for FNNs in [22], we first derive a more general convergence result to the direction of a KKT point for t-NNs Lemma 9, and then goes deeper by using a constructive approach to establish the approximately transformed low-rankness in the proof of Thm 10.\n- Differing from [34] which focuses on standard FNN generalization, our approach delves into t-NNs' adversarial generalization. We achieve this by introducing the $(\\delta, r)$-parameterization, bounding localized Rademacher complexity for a Minkowski set in adversarial settings, and using low-tubal-rank approximations for tensor weights.\n\n**Q2** (Rank adaptivity for Thm 6).\n\n**Re:** The analysis of Thm 6 doesn't require rank adaptivity due to explicit constraints on weight tensor ranks. Yet, we appreciate exploring alternative rank-adaptive methods like [x, y] due to the potential value for practical adversarial training of t-NNs.\n\n**Q3** (Empirical studies on robustness and low-rankness for standard NNs rather than t-NNs).\n\n**Re:** We recognize that the relationship between weight low-rankness and enhanced robustness is actively researched, yielding diverse observations and results. Direct comparisons should be approached cautiously, as these studies primarily concern standard network architectures and may not seamlessly apply to t-NNs. We'll incorporate insights from [a-d] into our discussion at line 250, highlighting the distinctions between standard networks and t-NNs with careful references. Additionally, we're planning to introduce new experiments (e.g., Experiment II in \"Contributions and Numerical Evaluations\") that employ t-NNs' own results to substantiate our claims."}, {"review_id": "WVJTpmos8E", "reviewer": "Reviewer_yC9Y", "summary": "The paper analyzes the generalization ability of t-product layers (t-NNs) by deriving upper bounds on generalization error in standard and adversarial settings.", "questions": "Is Definition-1 (t-product) equivalent to the batch matrix-multiplication operation, where `c` corresponds to the batch dimension?\nIs Definition-3 (t-SVD) equivalent to the SVD of a block-diagonal representation from Definition 2?\nWhy do these concepts need special terms? What is the advantage of such complex structures over the traditional deep learning layers? \n", "limitations": "Discussed in the Conclusion. ", "rating": 4, "confidence": 1, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "The paper advances the theoretical understanding of t-NNs and derives their generalization behavior in two practical settings.", "weaknesses": "The paper focuses on and is written about t-product layers, referenced as [7, 28] in the first lines of the introduction. The first reference is a patent, and the second is a paper from 2018 (from the same authors as the patent), introducing the concept more or less academically. The submission assumes the reader's familiarity with these concepts right from the start, which is a mistake, and does not attempt to clarify or recap the importance of these concepts up until Sec. 3. From this standpoint, the writing should be improved. \n\nThe importance of the usage of t-product layers in the Deep Learning community is not supported with sufficient evidence, leaving the question of the practical utility of the studied framework unanswered.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1** (Writing).\n\n**Response:**  Thanks for your comment on the writing.  \nFirstly, we would like to address the need for references to [7] and [28].\n- We appreciate your highlighting the reference to patent [7] for the scientific rigor and integrity of our work.  However, patent [7] (granted in Dec. 2022) has garnered a certain level of attention, evident from citations in two IEEE T-GARS papers (Google Scholar) and four patents (Google Patents). Additionally, we draw attention to instances where scientific papers [R2.1] have cited important patents. Therefore, we respectfully assert that citing [7] does not have any negative consequences.\n- The arXiv paper [28] introduced t-NNs and presented noteworthy advancements on MNIST and CIFAR-10 datasets, outperforming standard matrix networks. It furnishes compelling evidence of the potential of t-NNs in real-world benchmark tasks. As a result, t-NNs have found extensive applications in machine learning over recent years, as evidenced by [25, 30, 31, 40]. Thus, [28] should also be cited.\n\nSecondly, we apologize for any confusion and wish to clarify that we \"expect\" rather than \"strictly assume\" readers' familiarity with t-product layers in the introduction. As aptly noted by Reviewer 3 in the Strengths, \"Although this is a rather technical paper, the authors manage to present the findings comprehensively by rigorously introducing the relevant concepts with precise notation.\" We choose to briefly introduce the significance and recent advancements in t-NNs rather than the basic concepts within the introduction, due to the complexity of technical terms associated with t-NNs. To provide a smoother understanding for readers, we then revisit and recap the foundational concepts in subsequent sections. \n\nHowever, we totally understand that this may delay readers' eager comprehension of the concepts of t-NNs. To mitigate this concern, we will revise the introduction to provide a clearer and more comprehensive explanation of t-product layers, including the basic ideas on a conceptual level. Additionally, we will clarify and recap necessary notions of t-NNs in Section 2 rather than Section 3. \n\n[R2.1] Florsheim E B, et al. Immune sensing of food allergens promotes avoidance behaviour. Nature, 2023.\n\n**Weakness 2** (Practical utility of the studied framework). \n\n**Response:**  We respectfully disagree with this comment.  The importance of incorporating t-product layers in the deep learning community is substantiated by substantial evidence, showcasing their promising advantages across a range of domains. These advantages are clearly demonstrated in applications such as graph data augmentation, dynamic graph learning, code semantics embedding, seismic data processing,  and more [25, 30, 31, 40, R2.2]. \n\nWe reemphasize that T-NNs show great potential in advancing machine learning. They excel in capturing global features and complex patterns through transformed domain representations. The integration of low-rank structures, along with global feature attention, augments resilience and efficiency. Moreover, the utilization of low-rank decomposition streamlines the optimization of parameters, thus reducing storage requirements and enhancing computation speed.\n\n[R2.2] Yang J, et al. Toward interpretable graph tensor convolution neural network for code semantics embedding. ACM Transactions on Software Engineering and Methodology, 2023.\n\n**Question 1** (T-product vs batch matrix-multiplication operation). \n\n**Response:**  No, the t-product is not a direct equivalent of batch matrix multiplication in the original domain according to Def. 1. Instead, it corresponds to batch matrix multiplication in the transformed domain. Additionally, this unique property of the t-product allows for efficient and effective data and parameter processing by leveraging the advantages of both batch matrix multiplication and the transformed domain. By performing computations in the transformed domain, the t-product enables more complex and intricate operations to be carried out, leading to enhanced performance and versatility in various applications.\n\n**Question 2** (T-SVD vs SVD of a block-diagonal representation from Def. 2). \n\n**Response:**  Yes. Our Eq. (3) reveals that t-SVD is equivalent to the SVD of a block-diagonal representation per Def. 2.\n\n**Question 3** (Special terms of concepts). \n\n**Response:**  The t-product and t-SVD are distinct terms that differentiate them from traditional matrix operations and factorizations. They are vital in t-NNs due to the multi-channel data structure, requiring new tensor-specific mathematical operations. These concepts efficiently manipulate tensors while maintaining their structure, enhancing global correlation capture. The t-product and t-SVD enable specialized tensor operations, addressing tensor-related challenges and unlocking t-NNs' potential for better performance in processing multi-dimensional data.\n\n**Question 4** (The advantage of such complex structures over the traditional deep learning layers).\n\n**Response:**  T-NNs excel over traditional deep learning layers in handling complex multi-channel data. While conventional FC layers are limited to vectors and matrices, t-NNs utilize specialized tensor-centric operations (like t-product and t-SVD) to efficiently capture intricate correlations and preserve multi-channel structures. This approach allows t-NNs to better understand global patterns within the data, leading to enhanced performance across various applications.\nAdditionally, t-NNs possess other advantageous features, including global feature attention mechanisms, robustness against adversarial attacks, and parameter compression, further enhancing their capabilities. Leveraging these complex structures enables t-NNs to process high-dimensional multi-channel data more effectively, making them a promising choice for addressing the challenges posed by modern data types and advancing model performance and generalization."}, {"review_id": "5Ff3nLjpQt", "reviewer": "Reviewer_83W1", "summary": "\n\nThe paper \"Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networks\" considers neural networks with t-product layers, that encode the weights in tensor format equipped with the t-product as the corresponding tensor operation and ReLU activations.\nThe paper is an analytical work that derives upper bounds for the generalization error in t-NNs, using norm bound estimates. Further, the influence of low-rankedness of the Tensor structures on robust generalization is inspected in the setting of exact low-rankedness and  approximately transformed low-rankedness. Results show that low-rank t-NNs improve robust generalization properties. In particular, the Adverserial generalization bound for low-rank tNNs is shown to scale with the tubal rank of the tensors, instead of their dimension as in the full-rank setting. \nAdditional findings show that in an overparametrized setting t-NNs yield approximately low-rank weights during adversarial learning.  ", "questions": "\n- What is the intuition of the transformed t-product, i.e. what is the reason that the M matrix is needed? What is the special case of M being the identiy? \n- Theorem 6: Can this statement be related to \"standard\" matrix valued neural networks with low-rank factorizations? \n- Theorem 10: Are you able to validate the statement in a numerical example. It would be interesting to see, how the rank of a layer changes as J gets larger. ", "limitations": "The authors discuss the limitations of their work, which manifest in rather loose bounds on the generalization error. They provide a suggestion on how to mitigate this issue in future work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Although this is a rather technical paper, the authors manage to present the findings comprehensively by rigorously introducing the relevant concepts with a precise notation.\n- An extensive Appendix is provided to give an introduction to t-SVDs, and overview of previous work and technical details.\n- The theoretical results of the work are discussed and compared with previous works. ", "weaknesses": "- No code and no numerical examples are provided to support the presented results.\n\nAlthough this is a rather theoretical work, a small test case can improve the presentation of this paper tremendously. \nI think this is a strong paper that gives a multitude of insights. \n\nA brief explanation of the intuition behind t-NN layers would also be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to express our appreciation for your positive and thorough evaluation of our technical paper. Your acknowledgment of our dedication to presenting the research findings with rigor, the incorporation of an extensive appendix, and the thoughtful comparison with existing works has provided us with profound encouragement.\nWe are devoted to unlocking the potential of t-NNs for machine learning and are fully dedicated to rectifying the weaknesses and addressing the questions you have pointed out.\n\n**Weakness 1** (No code or numerical examples).\n\n**Response:**  Please refer to the initial numerical assessments in the rebuttal session titled \"Contributions and Numerical Evaluations.\" We'll share the code after a thorough numerical evaluation.\n\n**Weakness 2** (A small test case to improve the presentation).\n\n**Response:** We acknowledge the importance of incorporating a practical example and are exploring the potential to include a relevant illustration that complements our theoretical results.\n\n**Weakness 3** (Intuition behind t-NN layers)*.*\n\n**Response:**  The intuition behind t-NN layers lies in their ability to handle multi-channel data more efficiently compared to traditional deep learning layers. Unlike standard fully connected layers that collapse multi-dimensional data into vectors or matrices, t-NNs maintain the multi-channel structure of the data as tensors. This unique property of t-NNs allows them to capture complex correlations and dependencies in the data more effectively. By preserving the inherent structure of tensors, t-NN layers can better grasp the global context and interrelationships within the data, leading to improved performance in various applications ([25,30,31,40]). \n\nAdditionally, t-NNs leverage specialized mathematical operations like the t-product and t-SVD in the transformed domain [14], which further enhances their ability to process complex data efficiently. The transformed domain allows t-NNs to focus on essential features and patterns in the data while disregarding noise and irrelevant local details, resulting in improved stability and robustness, especially in the face of adversarial attacks [40].\n\n**Question 1** \n\n**Q1.1** (Intuition of the transformed t-product, i.e, the need of matrix M)\n\n**Response:**  The introduction of the transformed domain in the t-product is a pivotal aspect of t-NNs, offering distinct advantages in handling complex data. \nBy using the transform matrix M, t-NNs can map tensors to various domains, like Fourier or DCT. These domains offer unique data representations, aiding t-NNs in leveraging frequency domain low-rankness and global feature attention.\n\nOperating in the transformed domain enables t-NNs to capture global features and structures in high-dimensional data, enhancing their performance in various applications. This domain also helps filter noise and irrelevant details, making t-NNs more robust against adversarial attacks. Global feature attention mechanisms further improve t-NNs' pattern identification.\n\nMoreover, the transformed domain reduces parameters, enhancing computational efficiency for high-dimensional data. In conclusion, t-NNs benefit from transformed domains to model complex data effectively, enhance robustness, and improve efficiency, making them promising in machine learning.\n\n**Q1.2**  (M being the identity).\n\n**Response:** Indeed, when the transform matrix M is an identity matrix, the transformed domain becomes equivalent to the original domain, and the t-product reduces to the standard parallel matrix multiplication of the frontal-slices of factor tensors. In this scenario, we lose the opportunity to leverage the advantages offered by the transformed domain representations, which is a situation to be avoided in t-NNs. Thus, we usually avoid an identity transform matrix M to ensure that t-NNs can exploit the benefits of the transformed domain representations for enhanced performance, robustness, and efficiency in modeling complex data.\n\n**Question 2** (Theorem 6 related to \"standard\" matrix neural networks with low-rank factorizations).\n\n**Response:** Yes!  When the channel number c=1, the derived bound exactly recovers the corresponding bounds for classical fully connected neural networks. This result demonstrates the compatibility of our approach with traditional neural networks and highlights the versatility of our low-rank parameterization in various settings.\n\nFurthermore, our findings reveal that the adversarial generalization bound under low-rank parameterization exhibits a superior scaling behavior compared to standard (full-rank) neural networks. The improved scaling implies that networks with low-rank parameterization may require a smaller number of training examples to achieve the desired accuracy, leading to potential benefits such as reduced energy consumption, storage requirements, and computational cost. \n\n**Question 3** (Numerical evaluation for Theorem 10).\n\n**Response:** Yes, we have actively begun the numerical evaluations for Theorem 10. We totally agree that it is interesting to see how the rank of a layer changes as J gets larger, and are more than willing to conduct such numerical evaluations. However, we would like to acknowledge that our empirical findings indicate a substantial time investment. Even for a t-NN encompassing merely three t-product layers, an extensive commitment ranging from about 500 to 2,000 hours on our available computational resources is required to comprehensively study the implicit bias phenomena. As such, we have embarked on initial numerical experiments specifically concerning three t-product layers to explore the implicit bias towards transformed low-rankness. You can find preliminary numerical results in \"Experiment II\" in \"Contributions and Numerical Evaluations.\""}, {"review_id": "2eiCMM6ea4", "reviewer": "Reviewer_pKvo", "summary": "The paper provides a thorough investigation of the generalization behavior of t-NNs for the first time, which closes the gap between the practical success of t-NNs and their theoretical analysis. To be specific, the authors derived the upper bounds for the generalization gaps. The authors also propose that compressing t-NNs with a transformed low-rank structure will result in more efficient adversarial training and tighter bounds. In addition to that, the authors show that adversarial training with GF in highly over-parameterized settings results in t-NNs with approximately transformed low-rank weights, and derive the sharp adversarial generalization bounds in this scenario as well.", "questions": "- Instead of using adversarial training with GF in highly over-parameterized settings to train a approximately transformed low-rank t-NN, is it possible to apply some extra regularizations in training to achieve a better low-rank transformation, for example, LoRA?  ", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper provides a thorough investigation of the generalization behavior of t-NNs for the first time.\n- The authors provide the bound for t-NNs generalization gaps with firm proof.\n- The authors further explore the generalization bound of t-NNs with a transformed low-rank structure and show that there exists a training framework that will result in approximately transformed low-rank weights.\n- The work is well motivated and with firm theoretical evaluation.", "weaknesses": "- Only theoretical evaluation is provided. Some empirical evaluations regarding the approximately transformed low-rank weights are expected.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are truly grateful for your favorable evaluation of our work. Your recognition of our strengths, including the comprehensive investigation into t-NNs' generalization behavior, rigorous derivation of generalization bounds, and exploration of transformed low-rank structures, reinforces our commitment to unleash the potential of t-NNs for machine learning. \nWe would also like to take this opportunity to address the weakness you pointed out and provide answers to the question you raised.\n\n**Weakness:**  \n*Only theoretical evaluation is provided. Some empirical evaluations regarding the approximately transformed low-rank weights are expected.*\n\n**Response:**  \nThank you very much for your thoughtful suggestion.  \nWhile our paper primarily emphasizes theoretical findings, we recognize and appreciate the importance of incorporating numerical evidence to reinforce our conclusions. To that end, we have actively undertaken numerical evaluations, particularly utilizing the effective rank of the M-block-matrix of a weight tensor as a metric for approximate low-rankness transformation in Experiment II. Please review the preliminary numerical assessments presented in the rebuttal section titled \"Contributions and Numerical Evaluations,\" along with the accompanying PDF file.\n\n**Question:**  \n*Instead of using adversarial training with GF in highly over-parameterized settings to train a approximately transformed low-rank t-NN, is it possible to apply some extra regularizations in training to achieve a better low-rank transformation, for example, LoRA?*\n\n**Response:**  \nYes, it is possible to apply additional regularizations during training to achieve a better low-rank representation in t-NNs. Instead of relying solely on adversarial training with gradient flow in highly over-parameterized settings, these extra regularizations can potentially promote and enforce low-rankness in the network.  \n\nTo validate the concern regarding the addition of an extra regularization term, we performed a preliminary experiment. In this experiment, we incorporated the tensor nuclear norm (Ref. [45] in our paper) as an explicit regularizer to induce low-rankness in the transformed domain. Specifically, we add the tensor nuclear norm regularization to the t-NN with three t-product layer (D=128) in Experiment II with a regularization parameter 0.01, and keep the other settings the same as Experiment II. We explore how the effective ranks of tensor weights evolve with the epoch number with/without tubal nuclear norm regularization.   \n\nThe initial experimental results are depicted in Figure 8 of the attached PDF in \"Contributions and Numerical Evaluations\". According to the results Figure 8, it becomes evident that the introduction of the explicit low-rank regularizer significantly enforced low-rankness in the transform domain of the weight tensors, thereby confirming the suggestion."}]

Author rebuttal:
## **Contributions and Numerical Evaluations**

We thank all the reviewers for their valuable comments and suggestions. We first clarify our contributions and novelty again, and then report the initial numerical evaluations as suggested by Reviewers (R1, R3, R4). 

---

**Contributions & Novelty**

With the rise of t-NNs  in machine learning, our paper introduces a pioneering theoretical framework for t-NNs, enabling us to comprehend both their standard and robust generalization behaviors for the first time. The main contribution and novelty of this paper lie in an in-depth theoretical analysis of t-NNs, revealing key properties and robustness of this specialized type of neural networks.

- *Theoretical Characterization of Generalization Behavior:* Through the introduction of lemmas specifically designed for t-NNs, this paper establishes upper bounds on the generalization error for t-NNs in both standard and adversarial contexts.
- *Robustness Analysis of t-NNs:* The analysis shows that t-NNs with exactly and approximately transformed low-rank weights exhibit lower adversarial generalization bounds, highlighting the benefits of transformed low-rank weights in improving robustness and efficiency.
- *Impact of Adversarial Learning on Weight Tensors:* The investigation reveals a novel observation that weight tensors in over-parameterized t-NNs tend to exhibit an approximation of transformed low-rankness.
- *Influence of Transformed Low-rank Weights on Robust Generalization:* Through the precise derivation of adversarial generalization bounds, the importance of integrating transformed low-rank weights is emphasized as a means to strengthen the robustness of t-NNs.

---

**Experiment I**

To validate the generalization bound in Thm 6, we have conducted experiments on the MNIST dataset to explore the relationship between adversarial generalization gaps (AGP), weight tensor low-rankness, and training sample size. We consider binary classification of 3 and 7,  with FSGM attacks of strength 20/255. The t-NN consists of three t-product layers and one FC layer, with weight tensor dimensions of 28×28×28 for $\underline{\textnormal{W}}^{(1)}$ to $\underline{\textnormal{W}}^{(3)}$, and 784 for the FC weight **w**. As an input to the t-NN, each MNIST image of size 28×28 is treated as a t-vector of 28×1×28.

Thm 6 emphasizes: (i) lower weight tensor rank leads to smaller AGP bound, and (ii) AGP bound diminishes at a rate of $1/\sqrt{N}$ as $N$ increases. We explored this by conducting experiments, controlling the upper bounds $\textnormal{r}$ of the tubal-rank to 4 and 28 for low and full tubal-rank cases, and systematically increasing the number of training samples.

Fig. 1 in the PDF presents initial results. The curves indicate that t-NNs with lower rank weight tensors have smaller robust generalization errors. Interestingly, the adversarial generalization errors seem to follow a linear relationship with $1/\sqrt{N}$, approximately validating the generalization error bound in Theorem 6 by approximating the scaling behavior of the empirical errors.

---

**Experiment II**

We carried out experiments to confirm two theoretical statements related to the analysis of GF-based adversarial training.

*Statement 2.1*  Thm 10 reveals that, under specific conditions, well-trained t-NNs with highly over-parameterized adversarial training using GF show nearly transformed low-rank parameters.

*Statement 2.2*  Lem 22 asserts that the empirical adversarial risk approaches zero, and the F-norm of the weights grows infinitely as \( t \) approaches infinity.

In continuation of Experiment I, we focus on binary classification on MNIST under FGSM attacks. The t-NN is structured with three t-product layers and one FC layer, with weight dimensions set to D×28×28 for $\underline{\textnormal{W}}^{(1)}$, D×D×28 for $\underline{\textnormal{W}}^{(2)}$ and $\underline{\textnormal{W}}^{(3)}$, and 28D for the FC weight $\textbf{w}$. Our experiments involve setting values of D to 128 and 256, respectively, and we track the effective rank of each weight tensor, the empirical adversarial risk, and the F-norm of the weights as the number of epochs progresses. Since implementing gradient flow with infinitely small step size is impractical in real experiments, we opt for SGD with a constant learning rate and batch-size of 80, following the setting on fully connected layers in [22].

Note that fully observing implicit bias generally requires 10,000 to 40,000 epochs as shown in [22] for FNNs. This would take around 500 to 2,000 hours on our devices. *Due to time constraints in the rebuttal phase, we can only offer preliminary experimental results as initial support for our research statements.*

For Statement 2.1, we present preliminary results illustrating the progression of the effective ranks of the M-block-diagonal matrix of tensor weights in Figs. 2 and 3 for the settings D=128 and D=256, respectively. Notably, these results show that the effective ranks decrease as more epochs are executed, thereby confirming the influence of implicit bias on transformed low-rankness, as described in Statement 2.1.

For Statement 2.2, we present initial numerical findings depicting the progress of the empirical adversarial risk and the F-norm of the weights in Figs. 4 and 6 for D=128, and Figs. 5 and 7 for D=256, respectively. Unfortunately, due to time limitations, the program was only capable of running for less than 1/10th of the expected epochs. Nevertheless, these preliminary results exhibit a consistent pattern with the theoretical descriptions outlined in Statement 2.2 and the numerical results reported in [22] for adversarial training and [23] for standard training of FNNs. Specifically, we observe a decreasing trend in the empirical risk function and an increasing trend in the weight tensor's F-norm, which align with the expected behavior based on our theoretical framework and corroborate the numerical results presented in [22, 23].

Meta-review: In recent applications, multi-channel learning has garnered significant attention, particularly concerning neural networks utilizing t-product layers (t-NNs). These t-NNs have demonstrated promising performance due to novel feature mapping in the transformed domain. This paper aims to develop theory for such t-NNs. The authors claim to do this by deriving upper bounds on the generalization error of t-NNs in both standard and adversarial settings. Their analysis reveals that t-NNs, when compressed with an exact transformed low-rank parameterization, can achieve tighter adversarial generalization bounds compared to non-compressed models. Furthermore, the paper establishes sharp adversarial generalization bounds for t-NNs employing approximately transformed low-rank weights. These findings emphasize the potential of transformed low-rank parameterization in improving the robust generalization of t-NNs, providing insights for future research and development in this domain.

The reviewers liked the theoretical results for t-NNs and derives the generalization behavior. They expressed some concerns about lack of code/empirical evaluations, clarity of writing, and significance of the contributions. These concerns seem to be alleviated for most of the reviewers by the authors response. Hence I recommend acceptance.
Decision: Accept (poster)