An official website of the United States government
The classical static Schrödinger Bridge (SSB) problem, which seeks the most likely stochastic evolution between two marginal probability measures, has been studied extensively in the optimal transport and statistical physics communities, and more recently in machine learning communities in the surge of generative models. The standard approach to solve SSB is to first identify its Kantorovich dual and use Sinkhorn's algorithm to find the optimal potential functions. While the original SSB is only a strictly convex minimization problem, this approach is known to warrant linear convergence under mild assumptions. In this work, we consider a generalized SSB allowing any strictly increasing divergence functional, far generalizing the entropy functional x log(x) in the standard SSB. This problem naturally arises in a wide range of seemingly unrelated problems in entropic optimal transport, random graphs/matrices, and combinatorics. We establish Kantorovich duality and linear convergence of Sinkhorn's algorithm for the generalized SSB problem under mild conditions. Our results provide a new rigorous foundation for understanding Sinkhorn-type iterative methods in the context of large-scale generalized Schrödinger bridges.
more »
« less
Soft-constrained Schrödinger Bridge: a Stochastic Control Approach
Schrödinger bridge can be viewed as a continuous-time stochastic control problem where the goal is to find an optimally controlled diffusion process whose terminal distribution coincides with a pre-specified target distribution. We propose to generalize this problem by allowing the terminal distribution to differ from the target but penalizing the Kullback-Leibler divergence between the two distributions. We call this new control problem soft-constrained Schrödinger bridge (SSB). The main contribution of this work is a theoretical derivation of the solution to SSB, which shows that the terminal distribution of the optimally controlled process is a geometric mixture of the target and some other distribution. This result is further extended to a time series setting. One application is the development of robust generative diffusion models. We propose a score matching-based algorithm for sampling from geometric mixtures and showcase its use via a numerical example for the MNIST data set.
more »
« less
- PAR ID:
- 10515369
- Editor(s):
- Dasgupta, Sanjoy; Mandt, Stephan; Li, Yingzhen
- Publisher / Repository:
- PMLR
- Date Published:
- Journal Name:
- Proceedings of The 27th International Conference on Artificial Intelligence and Statistics
- Volume:
- 238
- ISSN:
- 2640-3498
- Page Range / eLocation ID:
- 4429-4437
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider the problem of finite-horizon optimal control of a discrete linear time-varying system subject to a stochastic disturbance and fully observable state. The initial state of the system is drawn from a known Gaussian distribution, and the final state distribution is required to reach a given target Gaussian distribution, while minimizing the expected value of the control effort. We derive the linear optimal control policy by first presenting an efficient solution for the diffusion-less case, and we then solve the case with diffusion by reformulating the system as a superposition of diffusion-less systems. We show that the resulting solution coincides with a LQG problem with particular terminal cost weight matrix.more » « less
-
How to steer a given joint state probability density function to another over finite horizon subject to a controlled stochastic dynamics with hard state (sample path) constraints? In applications, state constraints may encode safety requirements such as obstacle avoidance. In this paper, we perform the feedback synthesis for minimum control effort density steering (a.k.a. Schrödinger bridge) problem subject to state constraints. We extend the theory of Schrödinger bridges to account the reflecting boundary conditions for the sample paths, and provide a computational framework building on our previous work on proximal recursions, to solve the same.more » « less
-
Redβ is a protein from bacteriophage λ that binds to single-stranded DNA (ssDNA) to promote the annealing of complementary strands. Together with λ-exonuclease (λ-exo), Redβ is part of a two-component DNA recombination system involved in multiple aspects of genome maintenance. The proteins have been exploited in powerful methods for bacterial genome engineering in which Redβ can anneal an electroporated oligonucleotide to a complementary target site at the lagging strand of a replication fork. Successful annealing in vivo requires the interaction of Redβ with E. coli single-stranded DNA-binding protein (SSB), which coats the ssDNA at the lagging strand to coordinate access of numerous replication proteins. Previous mutational analysis revealed that the interaction between Redβ and SSB involves the C-terminal domain (CTD) of Redβ and the C-terminal tail of SSB (SSB-Ct), the site for binding of numerous host proteins. Here, we have determined the x-ray crystal structure of Redβ CTD in complex with a peptide corresponding to the last nine residues of SSB (MDFDDDIPF). Formation of the complex is predominantly mediated by hydrophobic interactions between two phenylalanine side chains of SSB (Phe-171 and Phe-177) and an apolar groove on the CTD, combined with electrostatic interactions between the C-terminal carboxylate of SSB and Lys-214 of the CTD. Mutation of any of these residues to alanine significantly disrupts the interaction of full-length Redβ and SSB proteins. Structural knowledge of this interaction will help to expand the utility of Redβ-mediated recombination to a wider range of bacterial hosts for applications in synthetic biology.more » « less
-
We propose a family of First Hitting Diffusion Models (FHDM), deep generative models that generate data with a diffusion process that terminates at a random first hitting time. This yields an extension of the standard fixed-time diffusion models that terminate at a pre-specified deterministic time. Although standard diffusion models are designed for continuous unconstrained data, FHDM is natu- rally designed to learn distributions on continuous as well as a range of discrete and structure domains. Moreover, FHDM enables instance-dependent terminate time and accelerates the diffusion process to sample higher quality data with fewer diffusion steps. Technically, we train FHDM by maximum likelihood estimation on diffusion trajectories augmented from observed data with conditional first hitting processes (i.e., bridge) derived based on Doob’s h-transform, deviating from the commonly used time-reversal mechanism. We apply FHDM to generate data in various domains such as point cloud (general continuous distribution), climate and geographical events on earth (continuous distribution on the sphere), unweighted graphs (distribution of binary matrices), and segmentation maps of 2D images (high-dimensional categorical distribution). We observe considerable improvement compared with the state-of-the-art approaches in both quality and speed.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Proceeding:
- The DOI is not currently available.
