Fitted Value Iteration Methods for Bicausal Optimal Transport

• URL: http://arxiv.org/abs/2306.12658v2
• Date: Thu, 2 Nov 2023 01:24:36 GMT
• Title: Fitted Value Iteration Methods for Bicausal Optimal Transport
• Abstract summary: We develop a fitted value iteration (FVI) method to compute bicausal optimal transport (OT) Based on the dynamic programming formulation, FVI adopts a function class to approximate the value functions in bicausal OT. We demonstrate that multilayer neural networks with appropriate structures satisfy the crucial assumptions required in sample complexity proofs.
• Score: 4.459996749171579
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a fitted value iteration (FVI) method to compute bicausal optimal transport (OT) where couplings have an adapted structure. Based on the dynamic programming formulation, FVI adopts a function class to approximate the value functions in bicausal OT. Under the concentrability condition and approximate completeness assumption, we prove the sample complexity using (local) Rademacher complexity. Furthermore, we demonstrate that multilayer neural networks with appropriate structures satisfy the crucial assumptions required in sample complexity proofs. Numerical experiments reveal that FVI outperforms linear programming and adapted Sinkhorn methods in scalability as the time horizon increases, while still maintaining acceptable accuracy.

Related papers

• Fixed-Point Neural Optimal Transport without Implicit Differentiation [3.4298729855744026]
  We propose an implicit neural formulation of optimal transport that eliminates adversarial min-max optimization and multi-network architectures.<n>Our key idea is to parameterize a single potential in the Kantorovich dual and reformulate the associated c-transform as a proximal fixed-point problem.<n>This yields a stable single-network framework in which dual feasibility is enforced exactly through proximal optimality conditions.
  arXiv  Detail & Related papers  (2026-05-11T16:22:06Z)
• When Bayesian Tensor Completion Meets Multioutput Gaussian Processes: Functional Universality and Rank Learning [53.17227599983122]
  Functional tensor decomposition can analyze multi-dimensional data with real-valued indices.<n>We propose a rank-revealing functional low-rank tensor completion (RR-F) method.<n>We establish the universal approximation property of the model for continuous multi-dimensional signals.
  arXiv  Detail & Related papers  (2025-12-25T03:15:52Z)
• Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models [55.07411490538404]
  We propose a novel parallel sampling method that improves adaptive complexity dependence on dimension $d$.<n>Our approach builds on parallel simulation techniques from scientific computing.
  arXiv  Detail & Related papers  (2024-12-10T11:50:46Z)
• 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)
• Federated Conditional Stochastic Optimization [110.513884892319]
  Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML. This paper proposes algorithms for distributed federated learning.
  arXiv  Detail & Related papers  (2023-10-04T01:47:37Z)
• Generative modeling of time-dependent densities via optimal transport and projection pursuit [3.069335774032178]
  We propose a cheap alternative to popular deep learning algorithms for temporal modeling. Our method is highly competitive compared with state-of-the-art solvers.
  arXiv  Detail & Related papers  (2023-04-19T13:50:13Z)
• Faster Adaptive Federated Learning [84.38913517122619]
  Federated learning has attracted increasing attention with the emergence of distributed data. In this paper, we propose an efficient adaptive algorithm (i.e., FAFED) based on momentum-based variance reduced technique in cross-silo FL.
  arXiv  Detail & Related papers  (2022-12-02T05:07:50Z)
• Contrastive Conditional Neural Processes [45.70735205041254]
  Conditional Neural Processes(CNPs) bridge neural networks with probabilistic inference to approximate functions of Processes under meta-learning settings. Two auxiliary contrastive branches are set up hierarchically, namely in-instantiation temporal contrastive learning(tt TCL) and cross-instantiation function contrastive learning(tt FCL) We empirically show that tt TCL captures high-level abstraction of observations, whereas tt FCL helps identify underlying functions, which in turn provides more efficient representations.
  arXiv  Detail & Related papers  (2022-03-08T10:08:45Z)
• A Stochastic Bundle Method for Interpolating Networks [18.313879914379008]
  We propose a novel method for training deep neural networks that are capable of driving the empirical loss to zero. At each iteration our method constructs a maximum linear approximation, known as the bundle of the objective learning approximation.
  arXiv  Detail & Related papers  (2022-01-29T23:02:30Z)
• Efficient Semi-Implicit Variational Inference [65.07058307271329]
  We propose an efficient and scalable semi-implicit extrapolational (SIVI) Our method maps SIVI's evidence to a rigorous inference of lower gradient values.
  arXiv  Detail & Related papers  (2021-01-15T11:39:09Z)
• Sequential Subspace Search for Functional Bayesian Optimization Incorporating Experimenter Intuition [63.011641517977644]
  Our algorithm generates a sequence of finite-dimensional random subspaces of functional space spanned by a set of draws from the experimenter's Gaussian Process. Standard Bayesian optimisation is applied on each subspace, and the best solution found used as a starting point (origin) for the next subspace. We test our algorithm in simulated and real-world experiments, namely blind function matching, finding the optimal precipitation-strengthening function for an aluminium alloy, and learning rate schedule optimisation for deep networks.
  arXiv  Detail & Related papers  (2020-09-08T06:54:11Z)
• Spatially Adaptive Inference with Stochastic Feature Sampling and Interpolation [72.40827239394565]
  We propose to compute features only at sparsely sampled locations. We then densely reconstruct the feature map with an efficient procedure. The presented network is experimentally shown to save substantial computation while maintaining accuracy over a variety of computer vision tasks.
  arXiv  Detail & Related papers  (2020-03-19T15:36:31Z)

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.