ترغب بنشر مسار تعليمي؟ اضغط هنا

A large deviation approach to optimal transport

126   0   0.0 ( 0 )
 نشر من قبل Christian Leonard
 تاريخ النشر 2007
  مجال البحث
والبحث باللغة English
 تأليف Christian Leonard




اسأل ChatGPT حول البحث

A probabilistic method for solving the Monge-Kantorovich mass transport problem on $R^d$ is introduced. A system of empirical measures of independent particles is built in such a way that it obeys a doubly indexed large deviation principle with an optimal transport cost as its rate function. As a consequence, new approximation results for the optimal cost function and the optimal transport plans are derived. They follow from the Gamma-convergence of a sequence of normalized relative entropies toward the optimal transport cost. A wide class of cost functions including the standard power cost functions $|x-y|^p$ enter this framework.



قيم البحث

اقرأ أيضاً

We study the problem of bounding path-dependent expectations (within any finite time horizon $d$) over the class of discrete-time martingales whose marginal distributions lie within a prescribed tolerance of a given collection of benchmark marginal d istributions. This problem is a relaxation of the martingale optimal transport (MOT) problem and is motivated by applications to super-hedging in financial markets. We show that the empirical version of our relaxed MOT problem can be approximated within $Oleft( n^{-1/2}right)$ error where $n$ is the number of samples of each of the individual marginal distributions (generated independently) and using a suitably constructed finite-dimensional linear programming problem.
The theory of large deviations has been applied successfully in the last 30 years or so to study the properties of equilibrium systems and to put the foundations of equilibrium statistical mechanics on a clearer and more rigorous footing. A similar a pproach has been followed more recently for nonequilibrium systems, especially in the context of interacting particle systems. We review here the basis of this approach, emphasizing the similarities and differences that exist between the application of large deviation theory for studying equilibrium systems on the one hand and nonequilibrium systems on the other. Of particular importance are the notions of macroscopic, hydrodynamic, and long-time limits, which are analogues of the equilibrium thermodynamic limit, and the notion of statistical ensembles which can be generalized to nonequilibrium systems. For the purpose of illustrating our discussion, we focus on applications to Markov processes, in particular to simple random walks.
Motivated by applications in model-free finance and quantitative risk management, we consider Frechet classes of multivariate distribution functions where additional information on the joint distribution is assumed, while uncertainty in the marginals is also possible. We derive optimal transport duality results for these Frechet classes that extend previous results in the related literature. These proofs are based on representation results for increasing convex functionals and the explicit computation of the conjugates. We show that the dual transport problem admits an explicit solution for the function $f=1_B$, where $B$ is a rectangular subset of $mathbb R^d$, and provide an intuitive geometric interpretation of this result. The improved Frechet--Hoeffding bounds provide ad-hoc upper bounds for these Frechet classes. We show that the improved Frechet--Hoeffding bounds are pointwise sharp for these classes in the presence of uncertainty in the marginals, while a counterexample yields that they are not pointwise sharp in the absence of uncertainty in the marginals, even in dimension 2. The latter result sheds new light on the improved Frechet--Hoeffding bounds, since Tankov [30] has showed that, under certain conditions, these bounds are sharp in dimension 2.
In this article we study and classify optimal martingales in the dual formulation of optimal stopping problems. In this respect we distinguish between weakly optimal and surely optimal martingales. It is shown that the family of weakly optimal and su rely optimal martingales may be quite large. On the other hand it is shown that the Doob-martingale, that is, the martingale part of the Snell envelope, is in a certain sense the most robust surely optimal martingale under random perturbations. This new insight leads to a novel randomized dual martingale minimization algorithm that doesnt require nested simulation. As a main feature, in a possibly large family of optimal martingales the algorithm efficiently selects a martingale that is as close as possible to the Doob martingale. As a result, one obtains the dual upper bound for the optimal stopping problem with low variance.
We initiate a study of large deviations for block model random graphs in the dense regime. Following Chatterjee-Varadhan(2011), we establish an LDP for dense block models, viewed as random graphons. As an application of our result, we study upper tai l large deviations for homomorphism densities of regular graphs. We identify the existence of a symmetric phase, where the graph, conditioned on the rare event, looks like a block model with the same block sizes as the generating graphon. In specific examples, we also identify the existence of a symmetry breaking regime, where the conditional structure is not a block model with compatible dimensions. This identifies a reentrant phase transition phenomenon for this problem---analogous to one established for Erdos-Renyi random graphs (Chatterjee-Dey(2010), Chatterjee-Varadhan(2011)). Finally, extending the analysis of Lubetzky-Zhao(2015), we identify the precise boundary between the symmetry and symmetry breaking regime for homomorphism densities of regular graphs and the operator norm on Erdos-Renyi bipartite graphs.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا