Provably Convergent Schr\"odinger Bridge with Applications to Probabilistic Time Series Imputation

• URL: http://arxiv.org/abs/2305.07247v4
• Date: Sun, 10 Sep 2023 15:38:31 GMT
• Title: Provably Convergent Schr\"odinger Bridge with Applications to Probabilistic Time Series Imputation
• Authors: Yu Chen and Wei Deng and Shikai Fang and Fengpei Li and Nicole Tianjiao Yang and Yikai Zhang and Kashif Rasul and Shandian Zhe and Anderson Schneider and Yuriy Nevmyvaka
• Abstract summary: We present a first convergence analysis of the Schr"odinger bridge algorithm based on approximated projections. As for its practical applications, we apply SBP to probabilistic time series imputation by generating missing values conditioned on observed data.
• Score: 21.27702285561771
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Schr\"odinger bridge problem (SBP) is gaining increasing attention in generative modeling and showing promising potential even in comparison with the score-based generative models (SGMs). SBP can be interpreted as an entropy-regularized optimal transport problem, which conducts projections onto every other marginal alternatingly. However, in practice, only approximated projections are accessible and their convergence is not well understood. To fill this gap, we present a first convergence analysis of the Schr\"odinger bridge algorithm based on approximated projections. As for its practical applications, we apply SBP to probabilistic time series imputation by generating missing values conditioned on observed data. We show that optimizing the transport cost improves the performance and the proposed algorithm achieves the state-of-the-art result in healthcare and environmental data while exhibiting the advantage of exploring both temporal and feature patterns in probabilistic time series imputation.

Related papers

• Estimating Causal Effects from Learned Causal Networks [56.14597641617531]
  We propose an alternative paradigm for answering causal-effect queries over discrete observable variables. We learn the causal Bayesian network and its confounding latent variables directly from the observational data. We show that this emphmodel completion learning approach can be more effective than estimand approaches.
  arXiv  Detail & Related papers  (2024-08-26T08:39:09Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  Noise-contrastive estimation(NCE) has been proposed by formulating the objective as the logistic loss of the real data and the artificial noise. In this paper, we study it a direct approach for optimizing the negative log-likelihood of unnormalized models.
  arXiv  Detail & Related papers  (2023-06-13T01:18:16Z)
• Transport with Support: Data-Conditional Diffusion Bridges [18.933928516349397]
  We introduce the Iterative Smoothing Bridge (ISB) to solve constrained time-series data generation tasks. We show that the ISB generalises well to high-dimensional data, is computationally efficient, and provides accurate estimates of the marginals at intermediate and terminal times.
  arXiv  Detail & Related papers  (2023-01-31T13:50:16Z)
• Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs [3.74142789780782]
  This paper studies the problem of forecasting general processes using a path-dependent extension of the Neural Jump ODE (NJ-ODE) framework citepherreraneural. We show that PD-NJ-ODE can be applied successfully to classical filtering problems and to limit order book (LOB) data.
  arXiv  Detail & Related papers  (2022-06-28T20:50:14Z)
• Linear-Time Probabilistic Solutions of Boundary Value Problems [27.70274403550477]
  We introduce a Gauss--Markov prior and tailor it specifically to BVPs. This allows computing a posterior distribution over the solution in linear time, at a quality and cost comparable to that of well-established, non-probabilistic methods.
  arXiv  Detail & Related papers  (2021-06-14T21:19:17Z)
• Diffusion Schr\"odinger Bridge with Applications to Score-Based Generative Modeling [24.46142828617484]
  Diffusion SB is an original approximation of the Iterative Proportional Fitting (IPF) procedure to solve the Schr"odinger Bridge problem. We present Diffusion SB, an original approximation of the Iterative Proportional Fitting (IPF) procedure to solve the SB problem, and provide theoretical analysis along with generative modeling experiments.
  arXiv  Detail & Related papers  (2021-06-01T17:34:27Z)
• Comparing Probability Distributions with Conditional Transport [63.11403041984197]
  We propose conditional transport (CT) as a new divergence and approximate it with the amortized CT (ACT) cost. ACT amortizes the computation of its conditional transport plans and comes with unbiased sample gradients that are straightforward to compute. On a wide variety of benchmark datasets generative modeling, substituting the default statistical distance of an existing generative adversarial network with ACT is shown to consistently improve the performance.
  arXiv  Detail & Related papers  (2020-12-28T05:14:22Z)
• Meta-Learning Stationary Stochastic Process Prediction with Convolutional Neural Processes [32.02612871707347]
  We propose ConvNP, which endows Neural Processes (NPs) with translation equivariance and extends convolutional conditional NPs to allow for dependencies in the predictive distribution. We demonstrate the strong performance and generalization capabilities of ConvNPs on 1D, regression image completion, and various tasks with real-world-temporal data.
  arXiv  Detail & Related papers  (2020-07-02T18:25:27Z)
• On the Convergence Rate of Projected Gradient Descent for a Back-Projection based Objective [58.33065918353532]
  We consider a back-projection based fidelity term as an alternative to the common least squares (LS) We show that using the BP term, rather than the LS term, requires fewer iterations of optimization algorithms.
  arXiv  Detail & Related papers  (2020-05-03T00:58:23Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.