# Lower and Upper Bounds on the VC-Dimension of Tensor Network Models

arXiv: https://arxiv.org/abs/2106.11827 · HTML: https://mlsanity.com/paper/2106.11827/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 71 references that are in the map.
- First posted on arXiv 22 Jun 2021.

## Builds on (most cited first, 26 of 26)

- [Tensorizing Neural Networks](https://mlsanity.com/paper/1509.06569/) (2015)
- [Tensor Ring Decomposition](https://mlsanity.com/paper/1606.05535/) (2016)
- [On the Expressive Power of Deep Learning: A Tensor Analysis](https://mlsanity.com/paper/1509.05009/) (2015)
- [Unsupervised Generative Modeling Using Matrix Product States](https://mlsanity.com/paper/1709.01662/) (2017)
- [Tensor-Train Recurrent Neural Networks for Video Classification](https://mlsanity.com/paper/1707.01786/) (2017)
- [Expressive power of tensor-network factorizations for probabilistic modeling, with applications from hidden Markov models to quantum machine learning](https://mlsanity.com/paper/1907.03741/) (2019)
- [Learning Relevant Features of Data with Multi-scale Tensor Networks](https://mlsanity.com/paper/1801.00315/) (2017)
- [Wide Compression: Tensor Ring Nets](https://mlsanity.com/paper/1802.09052/) (2018)
- [Efficient Low Rank Tensor Ring Completion](https://mlsanity.com/paper/1707.08184/) (2017)
- [Tensor Ring Decomposition with Rank Minimization on Latent Space: An Efficient Approach for Tensor Completion](https://mlsanity.com/paper/1809.02288/) (2018)
- [From probabilistic graphical models to generalized tensor networks for supervised learning](https://mlsanity.com/paper/1806.05964/) (2018)
- [Supervised Learning with Projected Entangled Pair States](https://mlsanity.com/paper/2009.09932/) (2020)
- [Expressive power of recurrent neural networks](https://mlsanity.com/paper/1711.00811/) (2017)
- [Scalable Gaussian Processes with Billions of Inducing Inputs via Tensor Train Decomposition](https://mlsanity.com/paper/1710.07324/) (2017)
- [Tensor Networks for Medical Image Classification](https://mlsanity.com/paper/2004.10076/) (2020)
- [Parallelized Tensor Train Learning of Polynomial Classifiers](https://mlsanity.com/paper/1612.06505/) (2016)
- [Tensor Regression Meets Gaussian Processes](https://mlsanity.com/paper/1710.11345/) (2017)
- [Tensor-Based Classifiers for Hyperspectral Data Analysis](https://mlsanity.com/paper/1709.08164/) (2017)
- [Tensor Completion by Alternating Minimization under the Tensor Train (TT) Model](https://mlsanity.com/paper/1609.05587/) (2016)
- [On Low-rank Trace Regression under General Sampling Distribution](https://mlsanity.com/paper/1904.08576/) (2019)
- [Quantum Tensor Networks, Stochastic Processes, and Weighted Automata](https://mlsanity.com/paper/2010.10653/) (2020)
- [Convex Tensor Decomposition via Structured Schatten Norm Regularization](https://mlsanity.com/paper/1303.6370/) (2013)
- [Optimal Estimation of Low Rank Density Matrices](https://mlsanity.com/paper/1507.05131/) (2015)
- [Partial Trace Regression and Low-Rank Kraus Decomposition](https://mlsanity.com/paper/2007.00935/) (2020)
- [Learning with tree tensor networks: complexity estimates and model selection](https://mlsanity.com/paper/2007.01165/) (2020)
- [On Tensor Train Rank Minimization: Statistical Efficiency and Scalable Algorithm](https://mlsanity.com/paper/1708.00132/) (2017)

## Built on by (most cited first, 1 of 1)

- [Potential and limitations of random Fourier features for dequantizing quantum machine learning](https://mlsanity.com/paper/2309.11647/) (2023)

## Abstract (arXiv)

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'erez-Garc'ia in [Cirac et al., 2019].