Reduced Contraction Costs of Corner-Transfer Methods for PEPS
- URL: http://arxiv.org/abs/2306.08212v1
- Date: Wed, 14 Jun 2023 02:54:12 GMT
- Title: Reduced Contraction Costs of Corner-Transfer Methods for PEPS
- Authors: Wangwei Lan, Glen Evenbly
- Abstract summary: We propose a pair of approximations that allows the leading order computational cost of contracting an infinite projected entangled-pair state to be reduced.
The improvement in computational cost enables us to perform large bond dimension calculations, extending its potential to solve challenging problems.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose a pair of approximations that allows the leading order
computational cost of contracting an infinite projected entangled-pair state
(iPEPS) to be reduced from $\mathcal{O}(\chi^3D^6)$ to $\mathcal{O}(\chi^3D^3)$
when using a corner-transfer approach. The first approximation involves (i)
reducing the environment needed for truncation of the boundary tensors (ii)
relies on the sequential contraction and truncation of bra and ket indices,
rather than doing both together as with the established algorithm. To verify
the algorithm, we perform benchmark simulations over square lattice Heisenberg
model and obtain results that are comparable to the standard iPEPS algorithm.
The improvement in computational cost enables us to perform large bond
dimension calculations, extending its potential to solve challenging problems.
Related papers
- $A^*$ for Graphs of Convex Sets [7.9756690088226145]
We present a novel algorithm that fuses the existing convex-programming based approach with information to find optimality guarantees.
Our method, inspired by $A*$, initiates a best-first-like procedure from a designated subset of vertices and iteratively expands it until further growth is neither possible nor beneficial.
arXiv Detail & Related papers (2024-07-24T16:48:32Z) - Efficiently Escaping Saddle Points for Non-Convex Policy Optimization [40.0986936439803]
Policy gradient (PG) is widely used in reinforcement learning due to its scalability and good performance.
We propose a variance-reduced second-order method that uses second-order information in the form of Hessian vector products (HVP) and converges to an approximate second-order stationary point (SOSP) with sample complexity of $tildeO(epsilon-3)$.
arXiv Detail & Related papers (2023-11-15T12:36:45Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties.
We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
arXiv Detail & Related papers (2023-10-18T10:29:58Z) - 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) - An Accelerated Stochastic Algorithm for Solving the Optimal Transport
Problem [2.1485350418225244]
A primal-dual accelerated gradient descent with variance reduction algorithm (PDASGD) is proposed to solve linear-constrained optimization problems.
PDASGD enjoys the best-known computational complexity -- $widetildemathcalO(n2/epsilon)$, where $n$ is the number of atoms, and $epsilon>0$ is the accuracy.
arXiv Detail & Related papers (2022-03-02T01:16:10Z) - Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth [1.9643748953805935]
We derive nonasymptotic complexity of exact and inexact PPA to minimize convex functions under $gamma-$Holderian growth.
Our numerical tests show improvements over existing restarting versions of the Subgradient Method.
arXiv Detail & Related papers (2021-08-10T07:15:07Z) - A stochastic linearized proximal method of multipliers for convex
stochastic optimization with expectation constraints [8.133190610747974]
We present a computable approximation type algorithm, namely the linearized proximal convex method of multipliers.
Some preliminary numerical results demonstrate the performance of the proposed algorithm.
arXiv Detail & Related papers (2021-06-22T07:24:17Z) - Correcting Momentum with Second-order Information [50.992629498861724]
We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product.
We validate our results on a variety of large-scale deep learning benchmarks and architectures.
arXiv Detail & Related papers (2021-03-04T19:01:20Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm.
We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound.
We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
arXiv Detail & Related papers (2021-01-19T04:24:23Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
We propose two single-timescale single-loop algorithms that require only one data point each step.
Our results are expressed in a form of simultaneous primal and dual side convergence.
arXiv Detail & Related papers (2020-08-23T20:36:49Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
A fundamental component of neural network verification is the computation of bounds on the values their outputs can take.
We propose a novel approach based on Lagrangian Decomposition.
We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
arXiv Detail & Related papers (2020-02-24T17:55:10Z)
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.