Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm

• URL: http://arxiv.org/abs/2406.09769v2
• Date: Mon, 17 Jun 2024 20:55:33 GMT
• Title: Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm
• Authors: Linjian Ma, Matthew Fishman, Miles Stoudenmire, Edgar Solomonik,
• Abstract summary: We introduce a method to efficiently approximate tensor network contractions using low-rank approximations. The proposed algorithm has the flexibility to incorporate a large portion of the environment when performing low-rank approximations.
• Score: 8.329034093208826
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tensor network contractions are widely used in statistical physics, quantum computing, and computer science. We introduce a method to efficiently approximate tensor network contractions using low-rank approximations, where each intermediate tensor generated during the contractions is approximated as a low-rank binary tree tensor network. The proposed algorithm has the flexibility to incorporate a large portion of the environment when performing low-rank approximations, which can lead to high accuracy for a given rank. Here, the environment refers to the remaining set of tensors in the network, and low-rank approximations with larger environments can generally provide higher accuracy. For contracting tensor networks defined on lattices, the proposed algorithm can be viewed as a generalization of the standard boundary-based algorithms. In addition, the algorithm includes a cost-efficient density matrix algorithm for approximating a tensor network with a general graph structure into a tree structure, whose computational cost is asymptotically upper-bounded by that of the standard algorithm that uses canonicalization. Experimental results indicate that the proposed technique outperforms previously proposed approximate tensor network contraction algorithms for multiple problems in terms of both accuracy and efficiency.

Related papers

• Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networks [19.185059111021854]
  We study the implicit bias of the general family of steepest descent algorithms, which includes gradient descent, sign descent and coordinate descent. We prove that an algorithm-dependent geometric margin starts increasing once the networks reach perfect training accuracy.
  arXiv  Detail & Related papers  (2024-10-29T14:28:49Z)
• Network-GIANT: Fully distributed Newton-type optimization via harmonic Hessian consensus [2.8617826964327113]
  We introduce a Newton-type fully distributed optimization algorithm, Network-GIANT, based on GIANT. We prove that our algorithm guarantees semi-global and exponential convergence to the exact solution over the network assuming strongly convex and smooth loss functions. We provide empirical evidence of the superior convergence performance of Network-GIANT over other state-of-art distributed learning algorithms such as Network-DANE and Newton-Raphson Consensus.
  arXiv  Detail & Related papers  (2023-05-13T11:42:40Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• Scalable computation of prediction intervals for neural networks via matrix sketching [79.44177623781043]
  Existing algorithms for uncertainty estimation require modifying the model architecture and training procedure. This work proposes a new algorithm that can be applied to a given trained neural network and produces approximate prediction intervals.
  arXiv  Detail & Related papers  (2022-05-06T13:18:31Z)
• Deep learning via message passing algorithms based on belief propagation [2.931240348160871]
  We present a family of BP-based message-passing algorithms with a reinforcement field that biases towards locally entropic distributions. These algorithms are capable of training multi-layer neural networks with discrete weights and activations with performance comparable to SGD-inspired solutions.
  arXiv  Detail & Related papers  (2021-10-27T16:52:26Z)
• Learning Structures for Deep Neural Networks [99.8331363309895]
  We propose to adopt the efficient coding principle, rooted in information theory and developed in computational neuroscience. We show that sparse coding can effectively maximize the entropy of the output signals. Our experiments on a public image classification dataset demonstrate that using the structure learned from scratch by our proposed algorithm, one can achieve a classification accuracy comparable to the best expert-designed structure.
  arXiv  Detail & Related papers  (2021-05-27T12:27:24Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks [56.084798078072396]
  We take a step towards closing the gap between theory and practice by significantly improving the known theoretical bounds on both the network width and the convergence time. We show that convergence to a global minimum is guaranteed for networks with quadratic widths in the sample size and linear in their depth at a time logarithmic in both. Our analysis and convergence bounds are derived via the construction of a surrogate network with fixed activation patterns that can be transformed at any time to an equivalent ReLU network of a reasonable size.
  arXiv  Detail & Related papers  (2021-01-12T00:40:45Z)
• Tensor Networks contraction and the Belief Propagation algorithm [0.0]
  Belief propagation is a well-studied message-passing algorithm that runs over graphical models. We show how it can be adapted to the world of PEPS tensor networks and used as an approximate contraction scheme.
  arXiv  Detail & Related papers  (2020-08-10T22:03:25Z)
• Algorithms for Tensor Network Contraction Ordering [0.0]
  Well-designed contraction sequences can dramatically reduce the contraction cost. We benchmark two common discrete optimization techniques to this ordering problem. We find that the algorithms we consider consistently outperform a greedy search given equal computational resources.
  arXiv  Detail & Related papers  (2020-01-15T19:00:07Z)

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.