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

• URL: http://arxiv.org/abs/2106.11827v1
• Date: Tue, 22 Jun 2021 14:39:25 GMT
• Title: Lower and Upper Bounds on the VC-Dimension of Tensor Network Models
• Authors: Behnoush Khavari, Guillaume Rabusseau
• Abstract summary: Network methods have been a key ingredient of advances in condensed matter physics. They can be used to efficiently learn linear models in exponentially large feature spaces. In this work, we derive upper and lower bounds on the VC dimension and pseudo-dimension of a large class of tensor network models.
• Score: 8.997952791113232
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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\'erez-Garc\'ia in [Cirac et al., 2019].

Related papers

• SpaceMesh: A Continuous Representation for Learning Manifold Surface Meshes [61.110517195874074]
  We present a scheme to directly generate manifold, polygonal meshes of complex connectivity as the output of a neural network. Our key innovation is to define a continuous latent connectivity space at each mesh, which implies the discrete mesh. In applications, this approach not only yields high-quality outputs from generative models, but also enables directly learning challenging geometry processing tasks such as mesh repair.
  arXiv  Detail & Related papers  (2024-09-30T17:59:03Z)
• Entangling Machine Learning with Quantum Tensor Networks [13.609946378021016]
  This paper examines the use of tensor networks, which can efficiently represent high-dimensional quantum states, in language modeling. We will abstract the problem down to modeling Motzkin spin chains, which exhibit long-range correlations reminiscent of those found in language. We find that the tensor models reach near perfect classifying ability, and maintain a stable level of performance as the number of valid training examples is decreased.
  arXiv  Detail & Related papers  (2024-01-09T00:07:36Z)
• Low-Rank Tensor Function Representation for Multi-Dimensional Data Recovery [52.21846313876592]
  Low-rank tensor function representation (LRTFR) can continuously represent data beyond meshgrid with infinite resolution. We develop two fundamental concepts for tensor functions, i.e., the tensor function rank and low-rank tensor function factorization. Our method substantiates the superiority and versatility of our method as compared with state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-12-01T04:00:38Z)
• Interaction Decompositions for Tensor Network Regression [0.0]
  We show how to assess the relative importance of different regressors as a function of their degree. We introduce a new type of tensor network model that is explicitly trained on only a small subset of interaction degrees. This suggests that standard tensor network models utilize their regressors in an inefficient manner, with the lower degree terms vastly underutilized.
  arXiv  Detail & Related papers  (2022-08-11T20:17:27Z)
• Patch-based medical image segmentation using Quantum Tensor Networks [1.5899411215927988]
  We formulate image segmentation in a supervised setting with tensor networks. The key idea is to first lift the pixels in image patches to exponentially high dimensional feature spaces. The performance of the proposed model is evaluated on three 2D- and one 3D- biomedical imaging datasets.
  arXiv  Detail & Related papers  (2021-09-15T07:54:05Z)
• Provable Lipschitz Certification for Generative Models [103.97252161103042]
  We present a scalable technique for upper bounding the Lipschitz constant of generative models. We approximate this set by layerwise convex approximations using zonotopes. This provides efficient and tight bounds on small networks and can scale to generative models on VAE and DCGAN architectures.
  arXiv  Detail & Related papers  (2021-07-06T17:00:29Z)
• Rank-R FNN: A Tensor-Based Learning Model for High-Order Data Classification [69.26747803963907]
  Rank-R Feedforward Neural Network (FNN) is a tensor-based nonlinear learning model that imposes Canonical/Polyadic decomposition on its parameters. First, it handles inputs as multilinear arrays, bypassing the need for vectorization, and can thus fully exploit the structural information along every data dimension. We establish the universal approximation and learnability properties of Rank-R FNN, and we validate its performance on real-world hyperspectral datasets.
  arXiv  Detail & Related papers  (2021-04-11T16:37:32Z)
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature [61.22680308681648]
  We show that global convergence is statistically intractable even for one-layer neural net bandit with a deterministic reward. For both nonlinear bandit and RL, the paper presents a model-based algorithm, Virtual Ascent with Online Model Learner (ViOL)
  arXiv  Detail & Related papers  (2021-02-08T12:41:56Z)
• Tensor-Train Networks for Learning Predictive Modeling of Multidimensional Data [0.0]
  A promising strategy is based on tensor networks, which have been very successful in physical and chemical applications. We show that the weights of a multidimensional regression model can be learned by means of tensor networks with the aim of performing a powerful compact representation. An algorithm based on alternating least squares has been proposed for approximating the weights in TT-format with a reduction of computational power.
  arXiv  Detail & Related papers  (2021-01-22T16:14:38Z)
• Connecting Weighted Automata, Tensor Networks and Recurrent Neural Networks through Spectral Learning [58.14930566993063]
  We present connections between three models used in different research fields: weighted finite automata(WFA) from formal languages and linguistics, recurrent neural networks used in machine learning, and tensor networks. We introduce the first provable learning algorithm for linear 2-RNN defined over sequences of continuous vectors input.
  arXiv  Detail & Related papers  (2020-10-19T15:28:00Z)
• Anomaly Detection with Tensor Networks [2.3895981099137535]
  We exploit the memory and computational efficiency of tensor networks to learn a linear transformation over a space with a dimension exponential in the number of original features. We produce competitive results on image datasets, despite not exploiting the locality of images.
  arXiv  Detail & Related papers  (2020-06-03T20:41:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.