Lower and Upper Bounds on the Pseudo-Dimension of Tensor Network Models
Authors: Behnoush Khavari
Guillaume Rabusseau
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Statistical Learning Theory
Tensor Networks
Generalization Bound
VC dimension
Tensor Decomposition Techniques
Tensor Train
Tensor Ring

Abstract: Tensor network methods have been a key ingredient of advances in condensed matter physics and have recently sparked interest in the machine learning community for their ability to compactly represent very high-dimensional objects. Tensor network methods can for example be used to efficiently learn linear models in exponentially large feature spaces [Stoudenmire and Schwab, 2016]. In this work, we derive upper and lower bounds on the VC dimension and pseudo-dimension of a large class of tensor network models for classification, regression and completion. Our upper bounds hold for linear models parameterized by arbitrary tensor network structures, and we derive lower bounds for common  tensor decomposition models~(CP, Tensor Train, Tensor Ring and Tucker) showing the tightness of our general upper bound. These results are used to derive a generalization bound which can be applied to classification with low rank matrices as well as linear classifiers based on any of the commonly used tensor decomposition models. As a corollary of our results, we obtain a bound on the VC dimension of the matrix product state classifier introduced in [Stoudenmire and Schwab, 2016] as a function of the so-called bond dimension~(i.e. tensor train rank), which  answers an open problem listed by Cirac, Garre-Rubio and Pérez-García in [Cirac et al., 2019].

Lower and Upper Bounds on the Pseudo-Dimension of Tensor Network Models
Behnoush Khavari DIRO & Mila
Guillaume Rabusseau DIRO & Mila, CIFAR Al Chair Université de Montréal grabusê i ro. amontreal.co ca
Université de Montréal
behnoush. khava r w www.nnteel..com ca
Abstract
Tensor network (TN) methods have been a key ingredient of advances condensed matter physics and have recently sparked interest in the machine learning commu- nity for their ability to compactly represent very high-dimensional objects. TN methods for example be used to efficiently learn linear models in exponen- tially large feature spaces [56]. In this work, we derive upper and lower bounds the VC-dimension and -ecudo-immensonn of large class of TN models for classification, regression and completion. Our upper bounds hold for linear models parameterized by arbitrary TN structures, and derive lower bounds for common tensor decomposition models (CP, Tensor Train, Tensor Ring and Tucker) showing the tightness of our general upper bound. These results used derive gener- alization bound which can be applied to classification with low-rank matrices as well linear classifiers based any of the commonly used tensor decomposition models. As a corollary of our results, we obtain a bound on the VC-dimension of the matrix product state classifier introduced [56] as a function of the so-called bond dimension (i.e. tensor train rank), which answers an open problem listed by Cirac, Rabro-Rubio and Pérez-Gareía in [13].
Introduction
Tensor networks (TNs) have emerged in the quantum physics community mean to compactly represent wave functions of large quantum systems [45, 5, 52]. Their introduction in physics can be traced back to the work of Penrose [47] and Feynman [15]. Akin to matrix factorization, TN methods rely on factorizing a high-order tensor into small factors and have recently gained interest from the machine learning community for their ability to efficiently represent and perform operations very high-dimensional data and high-order tensors. They have been for example successfully used for compressing models [43, 69, 42, 29, 70], developing new insights on the expressiveness of deep neural networks [14, 31] and designing novel approaches to supervised [56, 18] and unsupervised [55, 25, 39] learning. Most of these approaches leverage the fact that TN can be used to efficiently parameterize high-dimensional linear maps, which is appealing from two perspectives: it makes it possible to learn models in exponentially large feature spaces and acts as a regularizer, controlling the capacity of the class of hypotheses considered for learning.
While the expressive power of TN models has been studied recently [17, 2], the focus has mainly been on the representation capacity of TN models, but not on their ability to generalize in the context of supervised learning tasks. In this work, we study the generalization ability of TN models by deriving lower and upper bounds on the VC-dimension and pseudo-ding iseudo-dimension of TN models commonly used for classification, completion and regression, from which bounds on the generalization gap of TN models can be derived. Using the general framework of tensor networks, we derive a general upper bound for models parameterized by arbitrary TN structures, which applies to all commonly used tensor decomposition models [20] such as CP [27], Tucker [59] and tensor train (TT) [46], as well
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

as more sophisticated structures including hierarchical Tucker [19, 23], tensor ring (TR) [73] and projected entangled state pairs (PEPS) [60].
Our analysis proceeds mainly in two steps. First, we formally define the notion of TNN learning model by disentangling the underlying graph structure of TN from its parameters (the core tensors, or factors, involved in the decomposition).. This allows us to define, in a conceptually simple way, the hypothesis class Hg corresponding to the family of linear models whose weights are represented using an arbitrary TN structure G. We then proceed to deriving upper bounds on the VC/pseudo- dimension and generalization error of the class Ng. These bounds follow from a classical result from Warren [66] which was previously used to obtain generalization bounds for neural networks [3], matrix completion [54] and tensor completion [41]. The bounds we derive naturally relate the capacity of HG to the underlying graph structure G through the number of nodes and effective number of parameters of the TN. To assess the tightness of our general upper bound, we derive lower bounds for particular TN structures (rank-one, CP, Tucker, TT and TR). These lower bounds show that, for completion, regression and classification, our general upper bound is tight up to a log factor for rank-one, TT and TR tensors, and is tight up to a constant for matrices. Lastly, as corollary of our results, we obtain a bound on the VC-dimension of the tensor train classifier introduced in [56], which answers one of the open problems listed by Cirac, Garre-Rubio and Pérez-García in [13].
Related work Machine learning models using low-rank parametrization of the weights have been investigated (mainly from a practical perspective) for various decomposition models, including low-rank matrices [36, 49, 67], CP [1, 37, 7]. Tucker [35, 16, 26, 50J, tensor train [48, 10, 44, 56, 18, 53, 11, 65, 68] and PEPS [12]. From more theoretical perspective, generalization bounds for matrix and tensor completion have been derived in [54, 41] (based on the Tucker format for the tensor case). A bound on the VC-dimension of low-rank matrix classifiers was derived in [67] and bound on the pseudo-dimension of regression functions whose weights have low Tucker rank was given in [50] (for both these cases, we show that our results improve over these previous bounds, see Section 4.2). To the best of our knowledge the VC-dimension of tensor train classifiers has not been studied in the past, but the statistical consistency of the convex relaxation of the tensor completion problem was studied [58, 57] for the Tucker decomposition and in [28] for the tensor train decomposition. Lastly, in [38] the authors study the complexity of learning with tree tensor networks using the notion of metric entropy and covering numbers. They provide generalization bounds which are qualitatively similar to ours, but their results only hold for TN structures whose underlying graph is tree (thus excluding models such as CP, tensor ring and PEPS) and they do not provide lower bounds.
Summary of contributions We introduce a unifying frumework for TN-based learning models, which generalizes wide range of models based on tensor factorization for completion, classification and regression. This framework allows us to consider the class HG of low-rank TN models for a given arbitrary TN structure G (Section 3). We provide general upper bounds on the pseudo- diieeniin and VC-dimension of the hypothesis class He for arbitrary TN structure G for regression, classification and completion. Our results naturally relate the capacity of Hg to the number of parameters of the underlying TN structure G (Section 4.1). From these results, we derive generalization bound for TN-based classifiers parameterized by arbitrary TN structures (Theorem 4). We compare our results to previous bounds for specific decomposition models and show that our general upper bound is always of the same order and sometimes even improves on previous bounds (Section 4.2). We derive several lower bounds showing that our general upper bound is tight up to log factor for particular TN structures (Section 5). A summary of the lower bounds derived in this work, as well as upper bounds implied by our general result for particular TN structures, can be found in Table I at the end of the paper.
2 Preliminaries
In this section, we present basic notions of tensor algebra and tensor networks as well as generalization bounds based on combinatorial complexity measures. We start by introducing some notations. For any integer we use [k] to denote the set of integers from to k. We use lower case bold letters for vectors (e.g. v E IRd)), upper case bold letters for matrices (e.g. M E Rd xda) and bold calligraphic letters for higher order tensors (e.g. T E Rdi Rd4xd22 Xd2Xd1), ,. The inner product of two k-th order tensors
S, T E Igch x is defined by (T, = di Eij= Edi T Ti S Sq.... The outer product of
2

---

AB
(r(A)
= =x My
Figure 1: Tensor network representation of common operations matrices and vectors.
TWo vectors u E Rd and v E 2 is denoted by u @ V E Rddixds with elements (u Ø v)i.j V. The outer product generalizes to an arbitrary number of vectors. We use the notation (R2) to denote the space of p-th order hypereubie tensors of size d x d. We denote by y the space of functions f + y. sign(.) stands for the sign function. Finally, given a graph G = (V, F) and E} the set of edges incident the vertex v.
vertex
V, we denote by Ey E E
2.1 Tensors and Tensor Networks
Tensor networks A tensor T E Rdixxxxy can simply be seen as multidimensional array (T A.mii in E [dn], n E [p]). Complex operations on tensors can be intuitively represented using the graphical notation of tensor network (TN) diagrams [5, 45]. In tensor networks, p-th order
tensor is illustrated node with p edges (or legs) graph
An edge between two nodes
of a TN represents a contraction over the corresponding modes of the two tensors. Consider the
following simple TN with two nodes: and the second one a vector x E R Since this TN has one dangling leg (i.e. an edge which is not connected to any other node), it represents first order tensor, i.e. vector. The edge between the second leg of A and the leg of x corresponds to contraction between the second mode of A and the first mode of Hence, the resulting TN represents the classical matrix product which can be seen by
771 Y
X The first node represents matrix A E mxx
calculating the i-th component of this TN:
Σ, A:j = (Ax); Other examples of TN representations of common operations on matrices and vectors can be found in Figure 1. A special case of TN the tensor train decomposition [46] which factorizes a n-th order tensor in the form
This corresponds to
d2
T
T b1.22....hh
Σ
Σ
(9 (92) ... (9n-1)an 2 (9n)a. 1str
a1=1
On
where the tuple (r:)==) associated with the TT representation is called TT-rank.
Tensor network structures A tensor network (TN) be fundamentally decomposed in two constituent parts: a tensor network structure, which describes its graphical structure, and set of core tensors assigned each node. For example, the tensor in RRd xd2 Xdxxd, represented by the TN
is obtained by assigning the tensors T E Bdd xd and S Rxdxxx, to the
nodes of the TN structure
Formally, lensor network structure is given by a graph G (V, E, dim) where edges are labeled by integers: V is the set of vertices, E C (V x V) is a set of edges containing both classical edges (e V V) and singleton edges E V) and dim
assigns dimension to each edge in the graph. The set of singleton edges åG = E n V corresponds to the dangling legs of TN. Given a TN structure G, one obtains a tensor by assigning a core tensor T E 2 eg
Redi(()
to each vertex v in the graph, where E, = {e E E v E e). The resulting tensor, denoted by TN(G, (T") rev)). is a tensor of order [5G| in the tensor product space &e dRdim(e) Given a tensor structure G = (V, E, dim), the set of all tensors that can be obtained by assigning core tensors to the vertices of G is denoted by T(G) C 2cEba [Rdim(e):
T(G) (TN(G, (T" :
dim(l) V V).
3

---

CP
Tucker
Tensor Train
Tensor Ring
Hierarchical Tucker
PEPS
Figure 2: TN representation of common decomposition models for 4th order and 9th order tensors.
For CP, the black dot represents a hyperedge corresponding to a joint contraction over indices.
As an illustration, one can check that the set of m n matrices of rank at most r is equal to T to ".). Similarly, the set of 4th order d-dimensional tensors of TT rank at most is equal
Finally, for a given graph structure G, the number of parameters of any member of the family T(G) in Equation (2) (which the total number of entries of the core tensors
is given by
NG = Σ II dim(e)
(3)
VVV eE
This will be central quantity in the generalization bounds and bounds on the VC-dimension of TN models we derive in Section 4.
Common tensor network structures In Figure 2, we show the tensor network structures associated with classical tensor decomposition models such as CP. Tucker [59] and tensor train (TT) [46]. also known as matrix product state (MPS) [45, 52]. For the case of the Candecomp/Paraface (CP) decomposition [27], note that the TN structure a hyper-graph rather than a graph. We introduced the notion of TN structure focusing on graphs for clarity of exposition in the previous paragraph, but our formalism and results can be straightforwardly extended hyper-graph TN structures. In addition, we include the tensor ring (TR) [73] (also known as periodic MPS) and PEPS decompositions which have initially emerged quantum physics and recently gained interest in the machine learning community (see e.g.. [12, 62, 63, 71)). We also show the hierarchical Tucker decomposition initially introduced in [19, 23].
2.2
Generalization Bound and Complexity Measures
The goal of supervised learning is to learn a function f mapping inputs x E X to outputs y E y from sample of input-output examples S ((x1,91),,
(In, yn)} drawn independently and identically (i.i.d) from an unknown distribution D, where each y/ = f(x:). Given a set of hypotheses H C y one natural objective is find the hypothesis h H minimizing the risk R(h) (( ((((z), y) where f: y x y + R4 is loss function measuring the quality of the predictions made by h. However, since the distribution D is unknown, machine learning algorithms often rely on the empirical risk minimization principle which consists in finding the hypothesis h H that minimizes the empirical risk Rs(h) = n. Ei=1 E(h(ar)) ys). It is easy to see that the empirical risk an unbiased estimator the risk one of the concerns of learning theory is to provide guarantees on the quality of this estimator. Such guarantees include generalization bounds, which probabilistic bounds the generalization gap R(h) (h).. The generalization gap naturally depends on the size of the sample S, but also on the richness (or capacity, complexity) of the hypothesis class H.
In this work, our focus is on uniform generalization bounds, which bound the generalization gap uniformly for any hypothesis h E 7. as function of the size of the training sample and of the complexity of the hypothesis class H. While there are many ways of measuring the complexity of H. including VC-dimension, Rademacher complexity, metric entropy and covering numbers, we focus on the VC-dimension for classification tasks and its counterpart for real-valued functions, the pseudo-dine dinedd-immnnion, for completion and regression tasks.

---

Definition 1. Let H C. C (-1,+++1 +1} x be a hypothesis class. The growth function 1l N - N of H defined by
(x(n)) 8= (=
sup
I H)
The VC-dimension H. dY)(H), is the largest number of points 21, , In. shattered by H. i.e, for which K(h((11,....,
h E H}] = 2". . In other words: dvc(H) = sup(n [1x = 2n) }.
For a real-valued hypothesis class H. C "R* we say that H pseudo-shutters the points I1, ... Un E X with thresholds ti..... In E R, if for every binary labeling of the points ($1,..., E [-1,+1}" there exists h H. s.t. h(z,) < t, if and only if -1
The pseudo-dimension of a real-valued hypothesis class C RR,, Pdim(H)), is the supremum over for which there exist n. points that are pseudo-shuttered by H (with some thresholds).
Pseudo-dimension and VC-dimension combinatorial measures of complexity (or capacity) which can be used to derive classical uniform generalization bounds over a hypothesis class (see, e.g., [6, 40, 3)). By definition, the pseudo-dimension is related the notion of VC-dimension by the relation Pdim(H) = dvc(1(x, t) + sign(h(x) t) E H()
which holds for any H. I.*
3 Tensor Networks for Supervised Learning
In this section, we formalize the general notion of tensor network models. We then show how encompasses classical models such low-rank matrix completion [8, 9, 22, 51], classification [36, 49, 67], and tensor train based models [56, 18, 53, 11, 65, 68).
3.1 Tensor Network Learning Models
Consider classification problem where the input space X' is the space of p-th order tensors R4xxdxxxxxxx, One motivation for TN models is that the tensor product space X' can be expo- nentially large, thus learning linear model in this space is often not feasible. Indeed, the number of parameters of a linear classifier h X' + sign( (X, W)), where W Rdd x-dxx-xxppppp the tensor weight parameters, grows exponentially with p. TN models parameterize W as a low-rank TN, thus reducing the number of parameters needed to represent a model h. Our objective is to derive generalization bounds for the class of such hypotheses parameterized by low-rank tensor networks for classification, regression and completion tasks.
Formally, let G = (V, dim) be TN structure for tensors of shape d1 x ... X dp. i.e. where the set of singleton edges dG E V = {uI,-- ..., {p) and dim(v;) = de for each i E [p]. We are interested in the class of models whose weight tensors are represented in the TN structure G:
H Heggression = {h: + (W,X) IWWE E [(G)
(4)
HG Helassil (h: X sign (W, x)) (
(5)
HG
completton (h: (i,, ip) 1 W ii.....i W (IWWET T(G))
(6)
In Equation (6) for the completion hypothesis class, p-th order tensors are interpreted as real-valued functions/ f: [d1] x.]] [dp] + R over the indices of the tensor. Heompletion is thus a class of functions over the indices domain, for which the notion of pseudo-dimension is well-defined. This treatment of
completion as a supervised learning task was considered previously to derive generalization bounds for matrix and tensor completion [54, 41].
The benefit of TN models comes from the drastic reduction in parameters when the TN structure G is low-rank, in the sense that the number of parameters NG is small compared didz ......d, dz. In addition to allowing one to represent linear models in exponentially large spaces, this compression controls the capacity of the corresponding hypothesis class Hg.
3.2 Examples
To illustrate some TN models, we now present several examples of models based on common TN structures: low-rank matrices and tensor trains.
5

---

Low-rank matrices As discussed in Section 2.1, if we define the TN structure
Gmat (r) -
then mG (r)) is the set of matrices in Rd4 xd2 of rank at most r. The hypothesis class Heompletion Ginee (r)
then corresponds to the classical problem of low-rank matrix completion [8, 9, 22, 51], Similarly Helhssif
Gmat corresponds to the hypothesis class of low-rank matrix classifiers. This hypothesis class was previously considered, notably to compactly represent the parameters support vector machines for matrix inputs [36, 49, 67J. Lastly, for the regression case, (r)) is the set of functions {h X Tr(WX ) rrank S r). Learning hypotheses from this class relevant in, e-g.. quantum tomography, where it is known as the low-rank trace regression problem [24, 64, 30, 33].
Tensor train tensors The tensor train (TT) decomposition model [46] also known as matrix product state (MPS) in the quantum physics community [45, 52], has a number of parameters that grows only linearly with the order of the tensor. This makes the TT format an appealing model for compressing the parameters of ML models [56, 44, 17, 43). We now present the tensor train classifier model which was introduced in [56] and subsequently explored in [18]. Gíven vector input x E R", Stoudenmire and Schwab [56] propose to map x into high-dimensional space of p-th order tensors X = Rdx- xd by applying a local feature map Ø R F. to each component of the vector x and taking their outer product: (xx) = o(x1) @ xxx)) @ ...... @ ((xp) E (
Instead of relying on the so-called kernel trick, Stoudenmire and Schwab propose to directly learn the parameters W of a linear model h x + sign( (W, ((x))) in the exponentially large feature space X. The learning problem is made tractable by paremeterizing W low-rank TT tensor (see
Equation (1)). Letting
GTT(rI," "Tppi""""ppppi .Tp-1)
the hypothesis class considered in [56] is Horri which was extended in [18] and [53], tensor train classifiers were also previously considered in [1 65, 68). Similarly, the hypothesis class Horpplttion problem [21, 48, 61].
HGTT(r (m1," -pp-))" In addition to the approach of [56],
#Grr(r1 corresponds to the low-rank TT completion
Other TN models Lastly, we mention that our formalism can be applied to any tensor models having a low-rank structure, including CP, Tucker, tensor ring and PEPS. As mentioned previously, for the case of the CP dccomposition, the graph G of the TN structure is in fact hyper-graph with |V| p nodes and NG pdr parameters for weight tensor in (IRd) @r with CP rank at most r. Several TN learning models using these decomposition models have been proposed previously, including [26, 50] for regression in the Tucker format, [12] for classification using the PEPS model, [37, 7] for classification with the CP decomposition and [62, 72] for tensor completion with TR.
Pseudo-dimension and Generalization Bounds for Tensor Network Models
In this section, we give general upper bound on the VC-dimension and esis classes parameterized by arbitrary TN structures for regression, classification and completion. We then discuss corollaries of this general upper bound for common TN models including low-rank matrices and TT tensors, and compare them with existing results. Examples of particular upper bounds that can be derived from our general result can be found in Table 1.
of hypoth-
4.1 Upper Bounds on the VC-dimension, Pseudo-dimension and Generalization Gap
The following theorem states one of our main results which upper bounds the VC and pseudo- dimension of models parameterized by arbitrary TN structures.
Hrggesssoo Helassif H be the corresponding hypothesis classes defined in Equations (4-6), where each model has NG parameters (see Equation (3)).
Theorem 2. Let = (V, E, dim) be a tensor network structure and let H
complettoon
Then, Pdim CRimHHagme (eggessson) dvo(Heaany and PdimmHHar crmmllttion are all upper bounded by
2.o log

---

These bounds naturally relate the capacity of the TN classes HG fegresssion H H.G. number of parameters Ng of the underlying TN structure G. Following the analysis of [54] for matrix completion and its extension to the Tucker decomposition model presented in [41], the proof of this theorem leverages Warren's s theorem which bounds the number of sign patterns system of polynomial equations can take.
Hcoomletion to the
Theorem 3 ([66]). The number of sign patterns of n real polynomials, each of degree at most v, over N variables is at most (Aeun N for all ni > N (where e is Euler's number).
The proof of Theorem 2 fundamentally relies on Warren's 's theorem to bound the number of sign patterns that can be achieved by hypotheses in HG 7eegression on set of n input examples X. X.- Indeed, the set of predictions y/: = f((2,) for i E [n]] realizable by hypotheses h E HG Fefegression can be seen set of n polynomials of degree [V] over NG variables. The variables of the polynomials are the entries of the core tensors (T" eev The upper bound on the number of sign patterns obtained from Warren's theorem can then be leveraged obtain bound on the pseudo-dimension
of the hypothesis class HG H which in turn implies the upper bounds on dyc (R and (aimm The complete proof of Theorem 2 can be found in Appendix A.1.1.
Note that Theorem 2 implies that for fixed number of parameters NG, the VC-dimension grows with the number of vertices in the TN, thus a higher-order tensorization increases the capacity as measured by the VC dimension. This supports common observation that higher-order tensorizations of high-ding nigh-dimensional data generally result in a model with better learning capacity.
The bounds the VC-dimension and ascudo-dimensse presented in Theorem 2 can be leveraged to derive bounds on the generalization error of the corresponding learning models; see for example [40]. In the following theorem, we derive such generalization bound for classifiers parameterized by arbitrary TN structures.
Theorem 4. Let S be a sample of size n from a distribution D and let be a loss bounded by
1. Then, for any >> 0, with probability at least 1 - 8 over the choice of S, for any h E Hel
2
Sen|V| NG
+ log 5)
4)
R(h) < (h) + + NG log
The proof of this theorem, which can be found in Appendix A.1.2, relies on a symmetrization lemma and corollary of Hoeffding's inequality. It follows from this theorem that, with high probability, the
generalization gap R(h)- - (h) of any hypothesis h E Helaasi is in O No log (n) This bound
naturally relates the sample complexity of the hypothesis class with its expressiveness. The notion of richness of the hypothesis class appearing in this bound reflects the structure of the underlying TN through the number of parameters Ng. Using classical results (see, e.g., Theorem 10.6 [40]), similar generalization bounds for regression and classification with arbitrary TN structures can be
obtained from the bounds on the pseudo-dimension of H "errrsssioon and Hommpletion derived in Theorem 2. To examine this upper bound in practice, we perform an experiment with low-rank TT classifiers on synthetic data which can be found in Appendix B.
In the next subsection, we present corollaries of our results for particular TN structures, including low-rank matrix completion and the TT classifiers introduced in [56].
4.2 Special cases
We now discuss special cases of Theorems 2 and 4 and compare them with existing results.
de and T(G (r)) be the set of d, x d2 matrices of rank at most r. this case, we have [V] = 2 and No = r(d1 + d2), and Theorems and give the following result.
Low-rank matrices Let (r) A م
Heaeession (r)), dvc (Neluaa ( and Pdim (alim?(cmmmn ( are all upper bounded by 10r(d, + d2). Moreover, with high probability over the choice of a sample S of size n drawn i...d.
Corollary 5. Pdim Pdim
7

---

from distribution D, the generalization gap R(h) (s) of any hypothesis h E Helaziff is
Guass (r)
O
r(d, +22) login)
This bound improves the one given in [67] where the VC-dimension of H-llassif G (r) is bounded by
r(di + d2) log(r(d) + d2)) (see Theorem in [67]). For the matrix completion case, our upper bound improves on the bound Pdim (iiim (Hema)))) S r(d1 + d2) log 16ed1 derived in [54]. In Section 5, we will derive lower bounds showing that the upper bounds on the VC/pseudo-dimense of Corollary 5 are tight up to the constant factor 10 for matrix completion, regression and classification.
Tensor train Let Grr(r)=
and T (GGT((r) be the set of tensors
TT rank at most r. In this case, we have [V| = and NG O (dpr") where max, d4. For this class of hypotheses, Theorems 2 and 4 give the following result.
Corollary 6. Pdim (HeiHHrrr ), dvc d (Hére) (;) and Pdim(HHrre
are all in O (dpra log(p)),
where d = max; dz. Moreover, with high probability over the choice of sample S of size drawn i..d. from distribution D, the generalization gap R(h) Rg(h) of any hypothesis h E Helwoy
in O
dpp log(n)
This result applies for the MPS model introduced in [56] and thus answers the open problem listed as Question in [13]. To the best of our knowledge, the VC-dimension of tensor train classifier models has not been studied previously and our work is the first to address this open question. The lower bounds we derive in Section show that the upper bounds on the VC/pseudo-dimensine of Corollary 6 are tight up to O (log(p)) factor.
Tucker We briefly compare our result with the ones proved in [41] for tensor completion and in [50] for tensor regression using the Tucker decomposition. For a Tucker decomposition with maximum rank r for tensors of size d1 x... dp with maximal dimension d max, d,, the number of parameters is in O (r² + dpr) and the number of vertices in the TN structure is + 1. In this case, Theorems and show that the VC/pseudo-dimensions are in O ((r" + dpr) log(p)) and the
generalization gap is in O (V ((PPtdrr) (rP+trr)looooo)) log(a) with high probability for any classifer parameterized
by a low-rank Tucker tensor. is worth observing that in contrast with the tensor train decomposition, all bounds have an exponential dependency the tensor order p. In [41]. the authors give upper bound on the analogue of the growth function for tensor completion problems which is equivalent to ours. In [50], the pseudo-dimension of regression functions whose weight parameters have low Tucker rank is upper-bounded by O ((r² + drp) log(pd 1)), which is looser than our bound due to the term d=-1 (though similar argument to the one we use in the proof of Theorem 4 can be used to tighten the bound given in [50]).
Tree tensor networks Lastly, we compare our result with the ones presented in [38] where the authors study the complexity of learning with tree tensor networks using metric entropy and covering numbers. The results presented in [38] only hold for TN structures whose underlying graph G is tree. Let G be tree and be loss function which is both bounded and Lipschitz. Under these assumptions, is shown in [38] that, for any h E HG regresssoon with high probability over the choice of a sample S of size n drawn i.i.d. from a distribution D, the generalization gap R(h) R(h) is in Ö(VNg/n). Theorem gives a similar upper bound in (( on the generalization gap of low-rank tensor classifiers. However, our results hold for any TN structure G. Thus, in contrast with our general upper bound (Theorem 2), the bounds from [38] cannot be applied to TN structures containing cycles such tensor ring and PEPS.
5 Lower Bounds
We now present lower bounds on the VC and pseudo-dimensions standard TN models: rank-one, CP, Tucker, TT and TR.

---

Table I: Summary of our results for common TN structures. Both lower and upper bounds hold for the VC/pseudo-dimension of Ha Hermmplltio and He for the corresponding TN structure G' (see Equations (4-6)). The upper bounds follow from applying our general upper bound (Theorem 2) to each TN structure. The lower bounds are proved for each TN structure specifically. Each lower bound is followed by the condition under which it holds in parenthesis (small font). Note that the two bounds for TT and TR hold for both TN structures.
rank one
CP
Tucker
TT/TR
Decomposition
08
Lower Bound
(d - 1)p
rd (r s 1o
pd (r (d))
rd ir s dl , p(r"d-1)
(condition)
(r = d.
Upper bound
2dp (applog(12))
2prdlog(12p)
log(24p)
2pr 2 log 12p)
Theorem 7. The VC-dimension and pseudo-dimension of the classification, regression and comple- tion hypothesis classes defined in Equations (4-6) for the rank-one, CP, Tucker, TT and TR tensor network structures satisfy the lower bounds presented in Table 1.
These lower bounds show that the general upper bound of Theorem is tight up to a O (log(p)) factor for rank-one, TT and TR tensors and is tight up to constant for low-rank matrices.
The proof of this theorem can be found in Appendix A.2. These lower bounds show that our general upper bound is nearly optimal (up a log factor in p) for rank-one, TT and TR tensors. Indeed, for rank-one tensors we have (d 1)p S Crank one < 2dp log(12p) and for TT and TR tensors of rank r d whose order p is a multiple of 3 we have p(r-dd - 1)/3 < ct CTT/TR S pp 2 log( 12p), where grank-on onn (resp. c, C.T/TRR denotes any of the VC/pseudo-dimension of the regression, classification and completion hypothesis classe associated with rank-one tensors (resp. rank TT and TR tensors). In addition, the lower bound for the CP case shows that our general upper bounds are tight up to constant for matrices. Indeed, for p = 2 and r S d the bounds for the CP case give rd S Cmmatrx < 20rd where C.aatrix denotes the VC/pseudo-dimensse x d matrices of rank most r.
of the hypothesis classes associated with
6 Conclusion
We derived a general upper bound on the VC and pseudo-dimension of large class of tensor models parameterized by arbitrary tensor network structures for classification, regression and completion. We showed that this general bound can be applied obtain bounds on the complexity of relevant machine learning models such as matrix and tensor completion, trace regression and TT-based linear classifiers. In particular, our result leads an improved upper bound on the VC-dimension of low- rank matrices for completion tasks. As corollary of our results, we answer the open question listed in [13] on the VC-dimension of the MPS classification model introduced in [56]. To demonstrate the tightness of our general upper bound, we derived series of lower bounds for specific TN structures, notably showing that our bound is tight up to a constant for low-rank matrix models for completion, regression and classification.
Future directions include deriving tighter upper bounds and/or lower bounds for the specific TN structures. This includes investigating whether our general upper bound can be tightened by removing the log factor in the number of vertices of the TN structure, deriving a stronger lower bound for CP (we conjecture our lower bound can be improved by factor for CP), and loosening the condition under which our stronger lower bound holds for TT and TR (for TR, we conjecture that a lower bound of 2 d) holds for any p 2 3 and r S d for some value of 1). Studying other complexity measures (e.g. Rademacher complexity) and extending recent data-dependant generalization bounds for overparameterized deep neural networks, such as the ones used [4, 34], to TN learning models worth pursuing. Finally, building upon the connection between the depth of convolutional arithmetic circuits and tensor network structures introduced in [14], it interesting to connect our result on the VC-dimension of tensor networks to the expressiveness and generalization ability of neural networks.

---

Acknowledgements
We thank Maude Lizaire for feedbacks and the anonymous reviewers for the useful comments. This research is supported by the Canadian Institute for Advanced Research (CIFAR Al chair program) and the Natural Sciences and Engineering Research Council of Canada (Discovery program, RGPIN- 2019-05949).
References
[1] Evrim Acar, Daniel M Dunlavy, Tamara G Kolda, and Morten Mørup. Scalable tensor factoriza- tions for incomplete data. Chemometrics and Intelligent Laboratory Systems, 106(1):41144)) -)6646,,
2011.
[2] Sandesh Adhikary, Siddarth Srinivasan, Jacob Miller, Guillaume Rabusseau, and Byron Boots. Quantum tensor networks, stochastic processes, and weighted automata. In The 24th Interna- tional Conference on Artificial Intelligence and Statistics, volume 130, 2021.
[3] Martin Anthony and Peter I. Bartlett. Neural network learning: Theoretical foundations. cambridge university press, 2009.
[4] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In International Conference Machine Learning. pages 254-263. PMLR, 2018.
[5] Jacob Biamonte and Ville Bergholm. Tensor networks in a nutshell. arXiv preprint arXiv:1708.00006. 2017.
[6] Olivier Bousquet. Stéphane Boucheron, and Gábor Lugosi. Introduction to statistical learning theory. In Summer School on Machine Learning, pages 169-207. Springer, 2003.
[7] Deng Cai, Xiaofei He, Ji-Rong Wen, Jiawei Han, and Wei- Ma. Support tensor machines for text categorization. Technical report, 2006.
[8] Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 96))7717-77,, 2009.
[9] Emmanuel J Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory, 56(5):2053-2080, 2010.
[10] Chuan Chen, Zhe-Bit Bin Wu, Zi-Tai Chen, Zi-Bin Zheng. and Xiong-Jun Zhang. Auto-weighted robust low-rank tensor completion via tensor-train. Information Sciences, 567:100-115, 2021.
[11] Zhongming Chen, Kim Batselier, Johan AK Suykens, and Ngai Wong. Parallelized tensor train learning of polynomial classifiers. IEEE transactions neural networks and learning systems, 29(10):4621-4632 2017.
[12] Song Cheng, Lei Wang, and Pan Zhang. Supervised learning with projected entangled pair states. arXiv preprint arXiv:2009. 299.09000..9932 2020.
[13] Juan Ignacio Cirac, José Rubio, and David Pérez-García. Mathematical open problems in projected entangled pair states. Revista Matemática Complutense, 92(3):579-599 2019.
[14] Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: A tensor analysis. In Proceedings of the 29th Conference on Learning Theory, volume 49, pages 698-728, 2016.
[15] Richard P Feynman. Quantum mechanical computers. Foundations physics, 16(6):507-531, 1986.
[16] Silvia Gandy, Benjamin Recht, and Isao Yamada. Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Problems, 27(2):020010, 2011.
[17] Ivan Glasser, Ryan Sweke, Nicola Pancotti, Jens Eisert, and J. Ignacio Cirac. Expressive power of tensor-network factorizations for probabilistic modeling. In Advances in Neural Information Processing Systems, pages 1496-1508, 2019.
[18] Ivan Glasser, Nicola Pancotti, and Ignacio Cirac. From probabilistic graphical models to generalized tensor networks for supervised learning. JEEE Access, 8:68169-66 1221669688888 182, 2020.
[19] Lars Grasedyck. Hierarchical singular value decomposition of tensors. SIAM Journal on Matrix Analysis and Applications, 31(4):2029-205 2010.
10

---

[20] Lars Grasedyck, Daniel Kressner, and Christine Tobler. A literature survey of low-rank tensor approximation techniques. CAMM-Miitiilngen, 36(1):53-78, 2013.
[21] Lars Grasedyck, Melanie Kluge, and Sebastian Kramer. Variants of alternating least squares tensor completion in the tensor train format. SIAM Journal on Scientific Computing, 37(5): A2424-A2450, 2015.
[22] David Gross.
Recovering low-rank matrices from few coefficients in any basis. IEEE Transac- tions on Information Theory, 57(3):1548- 1566, 2011.
[23] Wolfgang Hackbusch and Stefan Kühn. A new scheme for the tensor representation. Journal of Fourier analysis and applications, 15(5):706-77 70,22,02222, 2009.
[24] Nima Hamidi and Mohsen Bayati. On low-rank trace regression under general sampling distribution. arXiv preprint arXiv: 1904.08769 2019.
[25] Zhao-Yu Yu Han, Jun Wang, Heng Fan, Lei Wang, and Pan Zhang. Unsupervised generative modeling using matrix product states. Physical Review X. 8(3):03 2018.
[26] Zhi He, Jie Hu, and Yiwen Wang. Low-rank tensor learning for classification of hyperspectral image with limited labeled samples. Signal Processing, 145:12-25, 2018.
[27] Frank L Hitchcock. The expression of tensor or a polyadic as a sum of products. Journal of Mathematics and Physics, 6(1-4):164-18, 1927.
[28] Masaaki Imaizumi, Takanori Maehara, and Kohei Hayashi. On tensor train rank minimization Statistical efficiency and scalable algorithm. In Advances in Neural Information Processing Systems, pages 3930-3939, 2017.
[29] Pavel Izmailov, Alexander Novikov, and Dmitry Kropotov. Scalable gaussian processes with billions of inducing inputs via tensor train decomposition. In International Conference on Artificial Intelligence and Statistics, volume 84, 2018.
[30] Hachem Kadri, Stéphane Ayache, Riikka Huusari, Alain Rakotomamoniy, and Liva Ralaivola. Partial trace regression and low-rank kraus decomposition. In Proceedings of the 37th Interna- tional Conference on Machine Learning, volume 119, 2020.
[31] Valentin Khrulkov, Alexander Novikov, and Ivan V. Oseledets. Expressive power of recurrent neural networks. In Proc. of ICLR, 2018.
[32] Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51 (3):455-500, 2009.
[33] Vladimir Koltchinskii and Dong Xia. Optimal estimation of low rank density matrices. J. Mach. Learn. Res., 16(53):155--1792, 2015.
[34] Jingling Li, Yanchao Sun, Jiahao Su, Taiji Suzuki, and Furong Huang. Understanding gen- cralization in deep learning via tensor methods. In International Conference on Artificial Intelligence and Statistics, pages 504-515. PMLR, 2020.
[35] Ji Liu, Przemyslaw Musialski, Peter Wonka, and Jieping Ye. Tensor completion for estimating missing values in visual data. In JEEE 12th International Conference on Computer Vision, 2009.
[36] Luo Luo, Yubo Xie, Zhihua Zhang, and Wu-Jun Li. Support matrix machines. In Proceedings of the 32nd International Conference Machine Learning, volume 37, 2015.
[37] Konstantinos Makantasis, Anastasios D Doulamis, Nikolaos D Doulamis, and Antonis Nikitakis. bassor-based classification models for hyperspectral data analysis. IEEE Transactions on Geoscience and Remote Sensing, 56( 12):6684446888 2018
[38] Bertrand Michel and Anthony Nouy. Learning with tree tensor networks: complexity estimates and model selection. arXiv preprint 200i::0007.01163 2020.
[39] Jacob Miller, Guillaume Rabusseau, and John Terilla. Tensor networks for probabilistic sequence modeling. In The 24th International Conference on Artificial Intelligence and Statistics, volume 130. 2021.
[40] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.

---

[41] Maximilian Nickel and Volker Tresp. An analysis of tensor models for learning on structured data. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 272-287. Springer, 2013.
[42] Alexander Novikov, Anton Rodomanov, Anton Osokin, and Dmitry P. Vetrov. Putting mrfs on a tensor train. In Proceedings of the 31th International Conference on Machine Learning.
volume 32, 2014.
[43] Alexander Novikov, Dmitry Podoprikhin, Anton Osokin, and Dmitry P. Vetrov. Tensorizing
neural networks. In Advances in Neural Information Processing Systems 28, 2015.
[44] Alexander Novikov, Mikhail Trofimov, and Ivan Oseledets. Exponential machines. arXiv
preprint arXiv: 600.00375, 2016.
[45] Román Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states. Annals of Physics, 349: 117-158, 2014.
[46] Ivan V Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33(5): 2295-2317, 2011.
[47] Roger Penrose. Applications of negative dimensional tensors. Combinatorial mathematics and its applications, 1:221 1:221-244, 1971.
[48] Ho N Phien, Hoang D Tuan, Johann A Bengua, and Minh N Do. Efficient tensor completion: Low-rank tensor train. arXiv preprint arXiv: 1601 000000000,, 2016.
[49] Hamed Pirsiavash, Deva Ramanan, and Charless C. Fowlkes. Bilinear classifiers for visual recognition. In Advances in Neural Information Processing Systems, 2009.
[50] Guillaume Rabusseau and Hachem Kadri. Low-rank regression with tensor responses. In Advances in Neural Information Processing Systems, 2016.
[51] Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471-501, 2010.
[52] Uirich Schollwöck. The density- matrix renormalization group the age of matrix product states. Annals of physics, 326(1 1)966))99999 162, 2011.
[53] Raghavendra Selvan and Erik B Dam. Tensor networks for medical image classification. arXiv preprint arXiv:2004. 10076, 2020.
[54] Nathan Srebro, Noga Alon, and Tommi S. Jaakkola. Generalization error bounds for collabora- tive prediction with low-rank matrices. In Advances in Neural Information Processing Systems, 2004.
[55] E. Miles Stoudenmire. Learning relevant features of data with multi-scale tensor networks. Quantum Science and Technology. 3(3)00440 2018.
[56] Edwin Miles Stoudenmire and David J. Schwab. Supervised learning with tensor networks. In Advances in Neural Information Processing Systems, 2016.
[57] Ryota Tomioka and Taiji Suzuki. Convex tensor decomposition via structured schatten norm regularization. Advances in Neural Information Processing Systems, 2013.
[58] Ryota Tomioka, Taiji Suzuki, Kohei Hayashi, and Hisashi Kashima. Statistical performance of convex tensor decomposition. In Advances in Neural Information Processing Systems, 2011.
[59] Ledyard R Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 31 (3):279-311, 1966.
[60] Frank Verstracte, Valentin Murg, and J Ignacio Cirac. Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems. Advances in Physics, 57(2))143-2244 2008
[61] Wenqi Wang, Vaneet Aggarwal, and Shuchin Aeron. Tensor completion by alternating mini- mization under the tensor train (tt) model. arXiv preprint arXiv: 065800558 2016.
[62] Wenqi Wang, Vancet Aggarwal, and Shuchin Aeron. Efficient low rank tensor ring completion. In IEEE International Conference Computer Vision, 2017.
[63] Wenqi Wang, Yifan Sun, Brian Eriksson, Wenlin Wang, and Vaneet Aggarwal. Wide compres- sion: Tensor ring nets. 2018 IEEE Conference on Computer Vision and Pattern Recognition, 2018.
12

---

[64] Yazhen Wang et al. Asymptotic equivalence of quantum state tomography and noisy matrix completion. The Annals of Statistics, (053)2222-2504,, 2013.
[65] Yongkang Wang, Weicheng Zhang, Zhuliang Yu, Zhenghui Gu, Hao Liu, Zhaoquan Cai, Congjun Wang, and Shihan Gao. Support vector machine based on low-rank tensor train decomposition for big data applications. In 2017 12th IEEF Conference Industrial Electronics and Applications (ICIEA), pages 850-853, IEEE, 2017.
[66] Hugh E Warren. Lower bounds for approximation by nonlinear manifolds. Transactions of the American Mathematical Sociery, (33()):167-178 1968.
[67] Lior Wolf, Hueihan Jhuang, and Tamir Hazan. Modeling appearances with low-rank SVM. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2007.
[68] Xiaowen Xu, Qiang Wu, Shuo Wang, Ju Liu, Jiande Sun, and Andrzej Cichocki. Whole brain fmmi pattern analysis based on tensor neural network. IEEE Access, 6:29297-29305, 2018.
[69] Yinchong Yang, Denis Krompass, and Volker Tresp. Tensor-train recurrent neural networks for video classification. In Proceedings of the 34th International Conference Machine Learning, volume 70, 2017.
[70] Rose Yu, Max Guangyu Li, and Yan Liu. Tensor regression meets gaussian processes. In International Conference on Artificial Intelligence and Statistics, volume 84, 2018.
[71] Longhao Yuan, Jianting Cao. Xuyang Zhao, Qiang Wu, and Qibin Zhao. Higher-dimension tensor completion via low-rank tensor ring decomposition. In 2018 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), pages 1071-1076. IEEE, 2018.
[72] Longhao Yuan, Chao Li, Danilo Mandic, Jianting Cao, and Qibin Zhao. Tensor ring decomposi- tion with rank minimization on latent space: An efficient approach for tensor completion. In Proc. of AAAI, volume 33, pages 9151-9158, 2019.
[73] Qibin Zhao, Guoxu Zhou, Shengli Xie, Liqing Zhang, and Andrzej Cichocki. Tensor ring decomposition. arXiv preprint 1rXiv:1606.0553. 2016.
13


Reviews:
[{"review_id": "kRW_gySEP14", "reviewer": "Reviewer_rJuG", "summary": "The paper presents generalization bounds for arbitrary Tensor-based network learning models. By carefully defining the space of functions that can be defined by certain tensor decompositions, they upper bound and lower bound the VC and pseudo-dimension of direct regressors, classifiers, and completion setups, leading to simple generalization bounds.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Clarity:\na) The paper is extremely well written and easy to follow. The authors do a fantastic job in easing the reader through all relevant background and motivation, as well as clearly and simply explaining technical detail important for understanding various steps in their work. The paper is a pleasure to read.\n\nQuality:\nb) The results presented are both simple and interesting. While Tensor-based models have been more and more frequently used in machine learning pipelines, the analysis of these structures has been limited to simply describing the capacity of TNs and drawing equivalences to existing machine learning models (RNNs to TTs, CNNs to Hierarchical Tucker, etc). The results here provide a very simple foundation on which more standard learning theoretic analysis can be defined over tensor-based networks.\n\nc) I would have liked to see some more significant connections drawn with existing work on “expressive power” of networks ([13,30,16,2]), particularly on connecting their definitions of capacity to generalization as described here.\n\nNovelty:\nd) The theorems and bounds are somewhat simple, and while they do take advantage of specific tensor network constructions, end up typically reducing to a bounds loosely similar to an unconstrained space over the compressed number of parameters up to some log factor.\n\nOther:\nLiterature review seems fairly complete.\nI have looked briefly at the supplementary material and follow general proof directions but have not vetted the theoretical analysis thoroughly.\nSupplementary notebook allows for replication of basic experiment conduced in supplement.\n\nFinal Thoughts:\nAn argument could be made that the results are too basic (low novelty), but in my mind having this as a starting point for accessing generalization with tensor networks will be a valuable step in future theoretical analysis of TNs, as described by the authors in their conclusion.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I agree with the authors that the theoretical analysis presented here does not warrant any discussion of potentially negative societal impact. Limitations and future work are adequately discussed in the conclusion.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "U1f_kE47Reb", "reviewer": "Reviewer_sBQh", "summary": "This paper studies the Pseudo-dimension (also the VC-dimension for the classification task) of a class of learning models (including linear regression (Eq. 4) and classification (Eq. 5), and completion (Eq. 6) ), of which the weights are modeled by tensor networks (TNs). In the work, the authors give an upper bound on the Pseduo-dimension of the models (Thm. 2) and a generalization bound for classifiers (Thm. 4). Furthermore, the authors also discuss the lower-bounds for several specific TN models to demonstrate the tightness of the obtained upper-bounds up to a $\\mathcal{O}(\\log(p))$ factor.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Pros:**\n\n- The proposed results are important for researchers to understand how different TNs impact the learning capacity of the TN model.\n- In several cases, the new bounds are tighter than the one in the existing works.\n- The proof on Thm. 2  is simple yet smart, which would inspire the tensor researchers to explore more results on tensor learning  along this line in the future.\n\n### Some specific comments and questions:\n\n1. As illustrated by Thm. 2, the Pdim or dvc are bounded by $2N_G\\log(12\\vert{}V\\vert)$, where $N_G$ denotes the total number of the TN and $\\vert{}V\\vert$ corresponds to the order (or degree) of TN to model the weight tensor. Given a fixed $N_G$, may I say that a higher-order tensorization (i.e., a larger $\\vert{}V\\vert$) can generally (or always) result in better learning capacity of the model, if we ignore the training issues for higher-order tensor models? \n2. As shown in Thm. 3, the claim holds if $n>N>2$. Does it mean that the main results in the work cannot be used to interpret those over-parameterized models, which are popularly applied in the settings of deep learning?\n3. The results in the work seem to imply that the TN structures are not so important for the learning capacity, as long as the scale of $N_G$ and $\\vert{}V\\vert$ are guaranteed. This claim would impact the study on TN structure search if this inference is true.\n4. I'm curious if the proposed results can also be used to interpret a similar bound given in the following work?\n\n> *Li, Jingling, et al. \"Understanding generalization in deep learning via tensor methods.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2020.*", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately addressed the limitations of the work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5-6"}, "extra_text": {}}, {"review_id": "SP6ZRmcMpL", "reviewer": "Reviewer_1sdU", "summary": "This work considers the tensor network methods in machine learning. The major contributions are some new lower and upper bounds on the pseudo-dimension for a large class of TN models. The derived results can be applied to machine learning tasks which involves the tensor decomposition models.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\nThis work is well organized, the writing is clear and easy to follow. \n\nThe results are valid, there are proofs for each Theorem and Corollary stated in the paper. \n\nCons:\nIt is mentioned that the derived bound can be used in many machine learning tasks like matrix completion, regression, and classification problems. However, how these bounds can be used in these tasks and how these bounds can help improve performance or facilitate the analyses are not clear. It would be better that some discussions about this are included.\n\nIt would be better that some simple simulations like matrix completion were included to show the effect of the proposed method.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See Cons above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers clearly appreciated the paper, and asked a number of questions that triggered interesting exchanges with the authors, as well as a couple of useful clarifications.
The authors are encouraged to take into account these exchanges when preparing the final version of their manuscript.
Decision: Accept (Spotlight)