Light Schrödinger Bridge

• URL: http://arxiv.org/abs/2310.01174v3
• Date: Tue, 19 Mar 2024 15:14:39 GMT
• Title: Light Schrödinger Bridge
• Authors: Alexander Korotin, Nikita Gushchin, Evgeny Burnaev,
• Abstract summary: We develop a lightweight, simulation-free and theoretically justified Schr"odinger Bridges solver. Our light solver resembles the Gaussian mixture model which is widely used for density estimation. Inspired by this similarity, we also prove an important theoretical result showing that our light solver is a universal approximator of SBs.
• Score: 72.88707358656869
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite the recent advances in the field of computational Schr\"odinger Bridges (SB), most existing SB solvers are still heavy-weighted and require complex optimization of several neural networks. It turns out that there is no principal solver which plays the role of simple-yet-effective baseline for SB just like, e.g., $k$-means method in clustering, logistic regression in classification or Sinkhorn algorithm in discrete optimal transport. We address this issue and propose a novel fast and simple SB solver. Our development is a smart combination of two ideas which recently appeared in the field: (a) parameterization of the Schr\"odinger potentials with sum-exp quadratic functions and (b) viewing the log-Schr\"odinger potentials as the energy functions. We show that combined together these ideas yield a lightweight, simulation-free and theoretically justified SB solver with a simple straightforward optimization objective. As a result, it allows solving SB in moderate dimensions in a matter of minutes on CPU without a painful hyperparameter selection. Our light solver resembles the Gaussian mixture model which is widely used for density estimation. Inspired by this similarity, we also prove an important theoretical result showing that our light solver is a universal approximator of SBs. Furthemore, we conduct the analysis of the generalization error of our light solver. The code for our solver can be found at https://github.com/ngushchin/LightSB

Related papers

• Optimizing Unitary Coupled Cluster Wave Functions on Quantum Hardware: Error Bound and Resource-Efficient Optimizer [0.0]
  We study the projective quantum eigensolver (PQE) approach to optimizing unitary coupled cluster wave functions on quantum hardware. The algorithm uses projections of the Schr"odinger equation to efficiently bring the trial state closer to an eigenstate of the Hamiltonian. We present numerical evidence of superiority over both the optimization introduced in arXiv:2102.00345 and VQE optimized using the Broyden Fletcher Goldfarb Shanno (BFGS) method.
  arXiv  Detail & Related papers  (2024-10-19T15:03:59Z)
• Solving QUBOs with a quantum-amenable branch and bound method [0.3749861135832072]
  We describe and experimentally validate an exact classical branch and bound solver for quadratic unconstrained binary optimization problems. Our solver leverages cheap-to-implement bounds from the literature previously proposed for Ising models. We detail a variety of techniques from high-performance computing and operations research used to boost solver performance.
  arXiv  Detail & Related papers  (2024-07-29T17:13:01Z)
• Light and Optimal Schrödinger Bridge Matching [67.93806073192938]
  We propose a novel procedure to learn Schr"odinger Bridges (SB) which we call the textbf Schr"odinger bridge matching. We show that the optimal bridge matching objective coincides with the recently discovered energy-based modeling (EBM) objectives to learn EOT/SB. We develop a light solver (which we call LightSB-M) to implement optimal matching in practice using the mixture parameterization of the Schr"odinger potential.
  arXiv  Detail & Related papers  (2024-02-05T17:17:57Z)
• Generalized Schrödinger Bridge Matching [54.171931505066]
  Generalized Schr"odinger Bridge (GSB) problem setup is prevalent in many scientific areas both within and without machine learning. We propose Generalized Schr"odinger Bridge Matching (GSBM), a new matching algorithm inspired by recent advances. We show that such a generalization can be cast as solving conditional optimal control, for which variational approximations can be used.
  arXiv  Detail & Related papers  (2023-10-03T17:42:11Z)
• Building the Bridge of Schr\"odinger: A Continuous Entropic Optimal Transport Benchmark [96.06787302688595]
  We propose a novel way to create pairs of probability distributions for which the ground truth OT solution is known by the construction. We use these benchmark pairs to test how well existing neural EOT/SB solvers actually compute the EOT solution.
  arXiv  Detail & Related papers  (2023-06-16T20:03:36Z)
• Light Unbalanced Optimal Transport [69.18220206873772]
  Existing solvers are either based on principles or heavy-weighted with complex optimization objectives involving several neural networks. We show that our solver provides a universal approximation of UEOT solutions and obtains its generalization bounds.
  arXiv  Detail & Related papers  (2023-03-14T15:44:40Z)
• Solving Sensor Placement Problems In Real Water Distribution Networks Using Adiabatic Quantum Computation [9.2810884211586]
  We formulate the problem of correctly placing pressure sensors on a Water Distribution Network (WDN) as a optimization problem. We outline the QUBO and Ising formulations for the sensor placement problem starting from the network topology and few other features. We present a detailed procedure to solve the problem by minimizing its Hamiltonian using PyQUBO, an open-source Python Library.
  arXiv  Detail & Related papers  (2021-08-06T07:31:38Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)

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.