Estimation of Stationary Optimal Transport Plans

• URL: http://arxiv.org/abs/2107.11858v1
• Date: Sun, 25 Jul 2021 17:46:21 GMT
• Title: Estimation of Stationary Optimal Transport Plans
• Authors: Kevin O'Connor, Kevin McGoff, Andrew B Nobel
• Abstract summary: We study optimal transport problems in which finite-valued quantities evolve dynamically over time in a stationary fashion. We introduce estimators of both optimal joinings and the optimal joining cost. We extend the consistency and rate analysis to an entropy-penalized version of the optimal joining problem.
• Score: 4.662321040754878
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study optimal transport problems in which finite-valued quantities of interest evolve dynamically over time in a stationary fashion. Mathematically, this is a special case of the general optimal transport problem in which the distributions under study represent stationary processes and the cost depends on a finite number of time points. In this setting, we argue that one should restrict attention to stationary couplings, also known as joinings, which have close connections with long run average cost. We introduce estimators of both optimal joinings and the optimal joining cost, and we establish their consistency under mild conditions. Under stronger mixing assumptions we establish finite-sample error rates for the same estimators that extend the best known results in the iid case. Finally, we extend the consistency and rate analysis to an entropy-penalized version of the optimal joining problem.

Related papers

• New Perspectives on Regularization and Computation in Optimal Transport-Based Distributionally Robust Optimization [8.564319625930892]
  We study optimal transport-based distributionally robust optimization problems where a fictitious adversary, often envisioned as nature, can choose the distribution of the uncertain problem parameters by a prescribed reference distribution at a finite transportation cost.
  arXiv  Detail & Related papers  (2023-03-07T13:52:32Z)
• Estimating Latent Population Flows from Aggregated Data via Inversing Multi-Marginal Optimal Transport [57.16851632525864]
  We study the problem of estimating latent population flows from aggregated count data. This problem arises when individual trajectories are not available due to privacy issues or measurement fidelity. We propose to estimate the transition flows from aggregated data by learning the cost functions of the MOT framework.
  arXiv  Detail & Related papers  (2022-12-30T03:03:23Z)
• Distributed Unconstrained Optimization with Time-varying Cost Functions [1.52292571922932]
  The objective is to track the optimal trajectory that minimizes the total cost at each time instant. Our approach consists of a two-stage dynamics, where the first one samples the first and second derivatives of the local costs to periodically construct an estimate of the descent direction towards the optimal trajectory. To demonstrate the performance of the proposed method, a numerical example is conducted that studies tuning the algorithm's parameters and their effects on the convergence of local states to the optimal trajectory.
  arXiv  Detail & Related papers  (2022-12-12T23:59:54Z)
• Convergence Rates for Regularized Optimal Transport via Quantization [3.04585143845864]
  We study the convergence of divergence-regularized optimal transport as the regularization parameter vanishes. A novel methodology using quantization and martingale couplings is suitable for non-compact marginals.
  arXiv  Detail & Related papers  (2022-08-30T16:58:40Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• An improved central limit theorem and fast convergence rates for entropic transportation costs [13.9170193921377]
  We prove a central limit theorem for the entropic transportation cost between subgaussian probability measures. We complement these results with new, faster, convergence rates for the expected entropic transportation cost between empirical measures.
  arXiv  Detail & Related papers  (2022-04-19T19:26:59Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  We investigate non-batch optimization problems where the objective is an expectation over smooth loss functions. Our work builds on the STORM algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.
  arXiv  Detail & Related papers  (2021-11-01T15:43:36Z)
• Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport [0.483420384410068]
  We derive nearly tight and non-asymptotic convergence bounds for solutions of entropic semi-discrete optimal transport. Our results also entail a non-asymptotic and tight expansion of the difference between the entropic and the unregularized costs.
  arXiv  Detail & Related papers  (2021-10-25T06:52:45Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Variational Refinement for Importance Sampling Using the Forward Kullback-Leibler Divergence [77.06203118175335]
  Variational Inference (VI) is a popular alternative to exact sampling in Bayesian inference. Importance sampling (IS) is often used to fine-tune and de-bias the estimates of approximate Bayesian inference procedures. We propose a novel combination of optimization and sampling techniques for approximate Bayesian inference.
  arXiv  Detail & Related papers  (2021-06-30T11:00:24Z)
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication [61.60069865891783]
  We resolve the min-max complexity of distributed convex optimization (up to a log factor) in the intermittent communication setting. We present a novel lower bound with a matching upper bound that establishes an optimal algorithm.
  arXiv  Detail & Related papers  (2021-02-02T16:18:29Z)

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.