Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Pros:
This work is well organized, the writing is clear and easy to follow. 

The results are valid, there are proofs for each Theorem and Corollary stated in the paper. 

Cons:
It 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.

It would be better that some simple simulations like matrix completion were included to show the effect of the proposed method.
limitations_and_societal_impact: See Cons above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: Clarity:
a) 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.

Quality:
b) 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.

c) 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.

Novelty:
d) 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.

Other:
Literature review seems fairly complete.
I have looked briefly at the supplementary material and follow general proof directions but have not vetted the theoretical analysis thoroughly.
Supplementary notebook allows for replication of basic experiment conduced in supplement.

Final Thoughts:
An 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.

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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: **Pros:**

- The proposed results are important for researchers to understand how different TNs impact the learning capacity of the TN model.
- In several cases, the new bounds are tighter than the one in the existing works.
- 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.

### Some specific comments and questions:

1. 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? 
2. 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?
3. 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.
4. I'm curious if the proposed results can also be used to interpret a similar bound given in the following work?

> *Li, Jingling, et al. "Understanding generalization in deep learning via tensor methods." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.*
limitations_and_societal_impact: Yes, the authors adequately addressed the limitations of the work.
review_title: null

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)