Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA large deviation approach to optimal transport
133
0
0.0
(
0
)
Authors
Christian Leonard
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 distributions. 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 approach 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 surely 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 tail 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
