Lower and Upper Bounds on the VC-Dimension of Tensor Network Models
Not on the map. Why?
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].
Key facts. Cited by 1 paper 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
26 of 71 references.
References · 26
- 2015Tensorizing Neural Networkscited by 250
- 2016Tensor Ring Decompositioncited by 127
- 2015On the Expressive Power of Deep Learning: A Tensor Analysiscited by 97
- 2017Unsupervised Generative Modeling Using Matrix Product Statescited by 88
- 2017Tensor-Train Recurrent Neural Networks for Video Classificationcited by 59
- 2019Expressive power of tensor-network factorizations for probabilistic modeling, with applications from hidden Markov models to quantum machine learningcited by 55
- 2017Learning Relevant Features of Data with Multi-scale Tensor Networkscited by 51
- 2018Wide Compression: Tensor Ring Netscited by 50
- 2017Efficient Low Rank Tensor Ring Completioncited by 45
- 2018Tensor Ring Decomposition with Rank Minimization on Latent Space: An Efficient Approach for Tensor Completioncited by 42
- 2018From probabilistic graphical models to generalized tensor networks for supervised learningcited by 32
- 2020Supervised Learning with Projected Entangled Pair Statescited by 31
14 more
- 2017Expressive power of recurrent neural networkscited by 30
- 2017Scalable Gaussian Processes with Billions of Inducing Inputs via Tensor Train Decompositioncited by 28
- 2020Tensor Networks for Medical Image Classificationcited by 20
- 2016Parallelized Tensor Train Learning of Polynomial Classifierscited by 16
- 2017Tensor Regression Meets Gaussian Processescited by 12
- 2017Tensor-Based Classifiers for Hyperspectral Data Analysiscited by 10
- 2016Tensor Completion by Alternating Minimization under the Tensor Train (TT) Modelcited by 9
- 2019On Low-rank Trace Regression under General Sampling Distributioncited by 9
- 2020Quantum Tensor Networks, Stochastic Processes, and Weighted Automatacited by 9
- 2013Convex Tensor Decomposition via Structured Schatten Norm Regularizationcited by 8
- 2015Optimal Estimation of Low Rank Density Matricescited by 6
- 2020Partial Trace Regression and Low-Rank Kraus Decompositioncited by 5
- 2020Learning with tree tensor networks: complexity estimates and model selectioncited by 5
- 2017On Tensor Train Rank Minimization: Statistical Efficiency and Scalable Algorithmcited by 4
Built on by
Citing papers per year: 2023: 1.
1 paper.